It also means that overtime you can build up interesting NPCs, locations, etc. Part of that too is getting good visuals going; describe cramped markets bustling with people and overflowing the senses, dark sewers creeping deep under the ground, etc.
When they get lost be ready with all the interesting parts of the city you want to describe to them! Be ready to tell them about the mysterious Temple of Abandoned Children, the spired academic district where men on stilts chase drakes out of the eaves with curved sticks, the noisy and noisome Fisherwife's market where the produce comes with rumors, and the claustrophobic ghettos beneath the tanners' ward where mad beggars clutch at you and cannot be driven off even with kicks.
Have some interesting NPCs (this might just be a couple key words sketched on a sheet of paper) for them to meet so they don't hate you for getting them lost for an hour.
Put the place they're looking for on Potter's Street, and then have four Potter's Streets, a Potter's Row, and a Potter's Way within the city walls. Most NPCs are so indifferent as to seem unfriendly. When the players ask directions, NPCs ask which Potter's Street they're after and then grow impatient when the players don't know.
You get the idea. Oh, and make random stuff happen all the time when they're in the city.
A prince arrives from some distant desert kingdom with a dozen elephants and marches them through the city to present himself to the king. Then his elephants have to be turned around and put up at the caravansary, but the caravansary is totally unready and it creates a massive knot of traffic near the gate full of swearing freemen and swarthy drovers.
Plague comes to the city and a particular ward is completely locked down and quarantined.
A charter is granted to a powerful merchant family to create a glassblowers' guild and the potters' guild is threatened, causing an undercurrent of resentment and anger that boils over into covert violence in the blazing heat of August.
Stuff that doesn't directly involve the players but gives them the sense that this city is alive and dynamic. Unless the PCs are very powerful they should feel like they are a very minor part of what goes on in the city, the city does not know their name, and when they are gone the city will forget them. Just like I feel in Seoul!
For that old school feel, come up with a random table (either percentage or something smaller) and have each player roll on it; whether or not they compare notes is up to them. I recommend between 20-100 tidbits, just be sure to change them up now and again. Just one or two sentences each should be fine. If you've time and creativity, draw up an actual broadsheet (predecessor to today's newspapers) covering campaign city highlights and hand it to your literate PCs to read about all the happenings in your fair city.
Sometimes (especially as they grow more powerful), let the PCs hear accurate accounts, exaggerations, or downplaying of events they had a part in. To get the PC goats, have another group claim a PC adventure as their own - especially if the result of this adventure brings lots of fame to the false claimants.
To get a larger sense of the world, news and gossip could entail political dealings on a broad scale; war in this country, a king assassinated in that country, a colony being established by a third, etc.
Of course, there is no promise that the news, rumors, and gossip are 100% true (just like real life!). What PCs hear may also turn into adventure hooks, red herrings, or distractors from a dedicated story arc, should you have one. Flesh out the ones the PCs show interest in, and WALLAH! instant urban sandbox play.
It is likely death on plotted story arcs and balanced encounters, though. The former due to many rumors interesting to PCs may not deal with your story (in which case, PCs can hear gossip about how some other group won or lost that story) and balance may die if the PCs hear tales of a dragon lair and confront said dragon, which turns out to be ancient, colossal, annoyed, and hungry while your PCs are still at a level comparable to a quick snack for said dragon.
After you've done this, you can institute limits on their travel, they might not be able to enter the noble quarter until they've built up the right amount of contacts, they are prevented from entering the prison district because of an outbreak of disease, etc. This gives you flexibility and you don't have to create an area until the PCs enter it.
If they want to find a magic weapons shop, they may need to do a streetwise check. If the shop is in an alley or other out-of-the-way place, require a streetwise or dungeoneering check to get there. If they bomb the check, they get lost in a back alley, and probably encounter something hostile.
After visiting the same shop once or twice, the checks get much easier, and after a while they can make it there with no trouble. Suppose five successful trips there from a common location results in permanent knowledge.
Additionally, you may want to check out my compilation of structures that can be found in a city. Adding mundane detail can make someplace seem much more lively!
http://forums.gleemax.com/showthread.php?t=1193601
If they want to find a magic weapons shop, they may need to do a streetwise check. If the shop is in an alley or other out-of-the-way place, require a streetwise or dungeoneering check to get there. If they bomb the check, they get lost in a back alley, and probably encounter something hostile.
After visiting the same shop once or twice, the checks get much easier, and after a while they can make it there with no trouble. Suppose five successful trips there from a common location results in permanent knowledge.
Considering "Hey there's a castle, 6 taverns and 3 inns and a market, sweet!" I think of something like this,
The thing about a big city is that to get anything done (at a fair price) you have to be in the know. To be in the know you have to know who to know or at the very least know someone. Now you can head down to the market and pay ten times the price for what you want like everyone else, or you can get to know someone. Now the bartender at that tavern over there - he is in the know. Knowing him don't mean nothing cause he isn't someone to know, but if you get in with him then your in. Once your in he can help you get to know someone worth knowing. After you have that taken care of then you're in teh know and the real fun starts.
The thing about it is that this city runs on bargains and deals. You want to buy a house? You want to do something more than rent a room and pay triple what you should at this tavern, or do you want to get in on the deal? You got a lot of gold to bring to the table, and no small amount of skill. Play your cards right with the right person and you'll be getting your meals delivered to your room and your pillows fluffed by your own maids. Make the wrong enemies and before long you won't be able to so much as show your face anywhere in town. Here included!
If you have ever played Oblivion (Elder Scrolls - Bethesda) and tried to get a house in the place you know what I am talking about. Your renown and affiliations have to be in the right place or the guy living in the castle won't grant you a deed. You can hook up with the underbelly (theives guild) but that has all manner of consequences. Remember - Nobles don't go to the market - they have their goods delivered. If a noble comes down to the market or tavern its for some other reason than "making a purchase" ;)
As an aside, a city of a million inhabitants will have several castles, hundreds of inns, a thousand or more taverns, and scores of markets.
Sketch a map.
Mention that it takes at least an hour to walk anywhere. Probably longer.
More than one castle is unlikely. A ruler wouldn't want to set up a potential alternative centre of military power. There might be more than one palace: I think a reasonable number is one in the castle, a more spacious palace used in peace-time, and one or more even more spacious palaces outside the city; five to ten miles away is about right.
There will be a city wall. Any city that large will have outgrown its city wall several times over. There will be three or four more city walls, and the final city wall will have overspill as well.
But yes, there will be a lot of taverns in a city of a million people. It will certainly be divided into a lot of districts. Each district will have a market of its own. The central market, if there is one, will be huge. It will mostly deal in luxury goods. Anyone wandering around it will see a lot of foreigners. In D&D a city this large will probably attract extra-planar travellers: describe a few as the PCs wander around the market area. Eladrin and gnomes, shadar-kai, possibly even drow, probably one or two efreet. Describe how only a few obvious foreigners are gawking.
Rome had blocks of flats. Nothing says lots of people like a few high rises.
A large city will have to have some way of distributing water. Either there is a river running through the city, with tributaries, or there is a big aqueduct and several cisterns that store and distribute water. A big aqueduct is more impressive. Set a fight scene on the top of it. Byzantium had a population of half a million. The basilica cistern, the largest cistern in Byzantium stored 78,000 cubic metres of water. According to wikipedia, it's underground, 143m by 65m. Imagine an underground space filled with water and columns. Probably another atmospheric place to set a fight. Someone's threatening to poison it. Tell the players how big it is. Have an NPC exclaim with horror that the plot will poison the water for maybe a quarter of the city!
A city that large is either on a navigable river or on the sea-coast. It will have docks. There will be lots of ships. Byzantium had two big harbours. Have the PCs try to find a particular ship before the tide turns and it sails.
Make it confusing. Get lost. Make it unfriendly to strangers. Get in fights. Make it change right before their eyes. Go from one neighborhood to another and assault them with the differences, literally.
Something like that...
But of all the campaign stops, I'd have to say a giant city has to be one of the most challenging. Good luck!