- No, they aren't hugely unusual to find, since I believe there are a couple almost guaranteed to be discoverable outside the Core Worlds.
- Yes they are damn good.
They're basically brute-force battleships with fighters to help them. (If you're familiar with the Onslaught, they're very similar.) Really basic advice? Kit them out with a near-full set of either bombers or attack fighters (Broadswords), and give them a punchy weapons fit with an opposing damage type. You have two large missile mounts at your disposal. USE THEM, they're your main damage output alongside your fighters. Throw point defence in the medium and small slots, you can safely leave a couple of slots empty if you want to spend more ordnance points on other fittings.
If you favour something more balanced/supportish, try mixing in (or fully equipping it with) Talon wings, or a similar cheap/expendable fighter. Then put offensive weaponry all over the ship itself and treat the fighters like a swarm of angry bees.
(All this advice should apply for both AI and player-controlled Legions.)