What's so wrong about hexagons? Hexagons would also open up the possibility of truly (well, nearly) round worlds when used with interspaced pentagons. Imagine sheets of hexagons on the triangles of an icosahedron, line of hexagons on the edges and pentagons at the vertexes. It's not perfect, but as an option I think it would still be pretty playable and having a truly round world would be really neat. (I was contemplating this as a good template for civ2 sequel since before I even had heard of civ3.)
You could even just take the normal civ rules and place them on the different map with almost no changes. The only different is that there are two less tiles in the first ring of a city, so the total number of tiles in a city radius add up to 19, not 21. But that's really a tiny change, one I doubt that would need much if any changes in the rules.
Obviously this can't happen in civ3, but it would be a really cool option for an expansion pack or civ4. With the game fully 3D, envisioning the whole globe is feasible now.