Stacks of doom aren't just the AI. They're quite usable by the humans, too. You probably won't want 100 units on one tile, but it's usually more effective to send 3-4 offensive units plus possibly a couple defensive ones in at once than to spread them out where they're easier to pick off.
You're right that, except perhaps on a Tiny map, 3-5 cities is not going to be enough in Civ3. Whereas in Civ5, your citizens are more and more unhappy the more cities you build, in Civ3, people in general are happier and happier the more cities you build - because it's less overcrowded where they live. Civ5 will eventually de facto stop your expansion because your people are too unhappy, but Civ3 won't make you stop expanding because your people are too happy. The cities will become more corrupt, but it's more a case of diminishing returns (but still positive) than the negative returns that new cities provide for many centuries in Civ5.
"Keep going until there's no more land" is a decent rule of thumb. It might not always make sense to take worthless tundra or desert, but even so, if the alternative is the AI taking the land, you might still want to, just without as much hurry to do so. "Where" varies - as MysteryX said, resources are a primary motivator. Hills give a 50% defence bonus, which is significant, but only really useful in areas where you suspect you might be attacked - in Civ3, your core cities generally won't be attacked, so building on hills there isn't a big advantage.
Also, roads give you money in Civ3, instead of taking away your money like in Civ5. The idea is that increased commerce is going to more than offset the cost to keep the road in decent condition. So build roads wherever your citizens are working tiles, and don't be sparse with them.
In general I'd say Civ3 is also more difficult than Civ5. I can trounce the Civ5 AI on King, and could even in my first game, and I suspect I could probably beat it fairly well on Emperor, too, though I haven't tried. But a Monarch (equivalent of King) game in Civ3 is a challenge and I sometimes lose, whereas an Emperor game is a big challenge and I usually lose. So, I wouldn't expect to necessarily be able to reach Emperor level in Civ3 particularly soon.