In Civ4, just a standard Huge map. I can never remember map sizes in Civ4, but it's somewhere in the general range of what ThorHammerz mentioned. MAFs are the main reason I never successfully played larger maps. By the time I got a 64-bit OS, playing giant Civ4 maps had fallen on my list of life priorities, so Huge is still the biggest I've played.
In Civ3, I played a number of Vanilla Huge maps (180x180/2 = 16200 tiles). I also have one in-progress at 220x220/2 (24200 tiles). Much larger than that, and you hit the 512-city limit in Civ3. Vanilla Huge with 31 civs can take absolutely forever for AI turns on a late-2002-era Pentium 4, but it's stable with no MAFs, which was good enough for me.