My personal recommendations (in no particular order):
1) Traveller- regardless of system, one of the best SF games ever made. Essentially the D&D of SF RPGs.
2) RIFTS. Not the game, the campaign world. Use the flavor & settings and run it in a RPG system you like.
3) HERO or M&M. Good Supers games like these are damn flexible. You could run almost anything in either one- excellent news if you have a campaign idea bouncing around your head that you haven't found a good system for. HERO has a sci-fi setting called Star-Hero. I'm currently designing a War of the Worlds campaign to be run in either one, but leaning more towards M&M- Illithids & Beholders make great aliens, and the conversion from D&D to M&M would be easier than one to HERO.
(GURPS is also flexible enough and capable of doing much of the above, but I don't care for its mechanics and inconsistencies- which I understand have been improved in the latest edition. It has more than one SF setting, including a version of Traveller.)
4) Space: 1889. Like RIFTS, a game with an excellent setting with mechanics that some feel could be done better. No game- not even much newer ones like Etherscope- has captured the feel and flavor of HG Wells & Jules Verne so well.
5) Alternity. Like Traveller, its a good game all around.
6) Spaceship Zero. Like #4 above, this game does a good job of capturing the feel of a certain subset of sci-fi, in this case the Flash Gordon/Commando Cody type stuff.
7) MechWarrior or Mekton. The former is the RPG companion to BattleTech, and is grittier than the latter. Both good for playing guys & gals who fly big robots with lots of weapons.
8) Cyberpunk or ShadowRun. Like #4 & #6, great for simulating a particular genre.
9) Star Wars & Star Trek games. If you want to play Luke Skywalker or Captain Kirk, you should probably pick up one of these. Both franchises have multiple RPGs- I personally own Star Wars D20 and Prime Directive (original).
Other Sci-fi franchises have their own games as well- Bab-5, Firefly, Jericho and others are all out there.