Seconding the recommendations of M:TG and Cheapass games, and also suggesting this- If you like the Cheapass games, check the OoP games stores for things like:
1) The old MetaGames (now Steve Jackson games) like Ogre, G.E.V. and the watershed Melee/Wizard/In the Labyrinth RPG- 3 stats, design a PC in 5 minutes.
2) Old TSR boardgames like SAGA or Revolt on Antares
3) Old Task Force Games minigames like Ultrawarrior and Robots!
4) RoboRally
5) Crimson Skies (the original, not the WizKids version). Not that I'm knocking the WizKids version- I haven't played it.
6) Avalon Hill games like Acquire, Feudal, Starship Troopers (the original- I heard they changed it), and the various Empire Builder-system train games like Iron Dragon (AFAIK, the only fantasy RR building boardgame out there).
7) Flying Buffalo's Nuclear War series of games. Quite simply the funniest game ever made about armageddon!
8) Star Fleet Battles and Starfire are both classic starship combat games.
9) Frag!, Munchkin, and Lunch Money are all classics. Also check out Modern Art, Lord of the Rings (boardgame), Quarto and Cathedral.
10) I'm also a big fan of Chainmail, which became D&D miniatures game, and its European competitor, Confrontation. And a buddy of mine just presented me with HeroScape, a new, Chainmail-esque boardgame that looks pretty cool!