Off the top of my bad head, caveat emptor, MOO2 is the fastest and best intro. Things can get exciting fast in MOO2.
But before making a decision you might want to watch some videos. Space 4x is a wonderful and very large genre that you cannot exhaust.
Further info you might like.
http://www.youtube.com/watch?v=L4rFkoZXlv8 this is the beginning of the wonderful tutorial and play through of Master of Orion 2 by quill18. The first few videos will teach you a lot! Quill18 is a very good commentator, like him.
http://www.youtube.com/watch?v=S5aD7rxRexA is the start of a play through of Galciv 2 Twilight of the Arnor by GetDaved who is also a five star commentator.
While you are at it, do not overlook Sins of a Solar Empire Complete with all expansions.
http://www.youtube.com/watch?v=m0R5zo0-W3A&feature=related A play through by GetDaved starts here. Sins is RTS but not a button mash fest. You can pause it and look around and your empire and make changes. A demo of Sins is still around if you Google.
Galciv 2 and Sins are both on sale this weekend, 4/22/2011 over at Impulse Driven. The standalone Rebellion expansion of Sins will contain all of the prior games and add new content and features. It will be out late this year or early next.
Then too, there is Sword of the Stars. Sword of the Stars 2 is coming out later this year. There is also a demo of SoTS around, make sure you get the most recent.
There are a lot of these games. Just my two cents and my IMHO take a close look at MOO2 first. MOO2 the great grand daddy of them all. MOO2 has it all in very compact and easy to learn form. Once you learn MOO2, you will judge all other space 4x in the light of the old master. Assuming you are able to unimmerse yourself long enough to look!