For your first question, you should try giving it some time. It usually takes around 10 seconds to log into Gamespy from the "Internet Games" screen. Failing that, if it still doesn't work then you may need to change your firewall settings to allow you to play civilization - first of all, make sure that the game is "unblocked", and open the specific port (I think it's port 2054). I'm not sure on the exact specifics of how to do that, sorry, but I know a few people who do know so I could ask them if you wanted.
For your second question, yes, you can team up with people against other people or against AI if you so wish. However, it's often difficult to find the right kind of player for this kind of game in the games lobby once you login. From my own experience, many of the players there are after short, snappy (timed on the fastest timer), early war games. Also, often many are not good sports and will quit as soon as they are losing or as soon as they get bored. So I'd advise first checking around the multiplayer forums here and making a post if you want to find a person interested in playing a nice long "team" game, since people on the Civfanatics forum tend to be a lot more reliable in sticking to a game for the long haul (as opposed to looking for a 20-minute "blitz" game).
Hope that helps.