How to mitigate the intial luck factor in Race For The Galaxy?
In my experience, the most effective way to reduce luck at the beginning is to give players a choice of two start worlds. A world you know will be on the table the whole game is a much bigger deal than four cards, of which you'll likely only play one or two, and sometimes none. The implementation of Race for the Galaxy at keldon.net does this. (Side note: some of my friends think Rebel Freedom Fighters is overpowered. You can always just disallow a start world if you're in that camp.)

This said, I think you might be overstating the importance of the starting hand. It's not meaningless, but I can't reliably predict how well my game will go based on it. I've had scores over 100 when I started out with no clear path based on my start world and hand. You have to be willing to explore (+5) on the first turn sometimes. It really doesn't put you that far behind - at most one turn, and there's a good chance you'll get to piggy-back on someone else's develop/settle anyway. (Half the time you don't, it's because they explored too.) However it happens, each time you draw cards, it may completely change your game. Luck isn't just on the first turn, and I think that with a choice of two start worlds, the luck in the rest of the game will be more significant than the initial luck.

Finally, if you're not playing with the third expansion, maybe you should be. It adds the ability to do a one-time search for a chosen category of card; you can choose to search for a 1- or 2-cost windfall world (or 1- or 2-defense if you're going military). If you're really desperate to get going, it is more reliable than the +5 card explore on the first turn.

(Of your suggestions, I think mulligans are better - larger initial draws can improve average and good hands too. I think you'll probably be pretty satisfied with two start worlds, but if you do still want to allow mulligans, you might want to restrict it to "bad" hands by some definition, to keep from focusing too much on the mulligan decision, and possibly improving some okay hands.)