Major cities
The following cities have been described as 'big', 'huge' and 'massive'. Here's the latest official map. http://img715.imageshack.us/img715/2858/skyrimmap.png
Also, here's a map I made that also seperates the holds. Note, however, that it is slightly outdated. Markarth and Karthwasten need to be swapped around, and the ??? region is actually Pine Forest.
http://i767.photobucket.com/albums/xx316/randomguyface/6thmap.png?t=1297322848
Markarth
http://media1.gameinformer.com/imagefeed/screenshots/TheElderScrollsVSkyrim/TheElderScrollsVSkyrimMedia/Markarth01.jpg
Previously known as Markarth Side, Markarth is part of the hold known as "The Reach", and inside a large canyon with a river running through it. Confirmed to be an ancient Dwemer ruin on Twitter, and also a major city. Todd Howard also mentioned an ancient Dwemer ruin built into the side of a mountain now inhabited by current Skyrim residents. The Dwemer style is quite different from that seen in previous games, but it is possible more similar Dwemer style things inside buildings/ruin areas. Much of it is built directly into the walls, but there are also some standalone buildings, and it is built mostly of white stone, with orange-brown roof tiles. According to UESP, conatins an Imperial College of the Voice. http://www.uesp.net/wiki/Lore:Markarth_Side
http://cdn.zenimax.com/akqacms/files/tes/concept_art/MarkarthCastleExterior.jpg
NOTE: Ithas been suggested to me that Markarth may actually be a renamed Karthwasten (being closer to this location on the arena map) while Markarth Side is a seperate settlement, and that the canyon is named Markarth, thus earning the names. I think this isprobably not the case, as settlements have been relocated before on maps (even Whiterun is in a different place to the Oblivion map) but I am listing the theory here anyway, as it is a reasonable possiblity.
Riften
http://i801.photobucket.com/albums/yy297/b_harrison/misc/artofskyrim_004_town.jpg
Located in the hold of "Rift", Riften is a major city on the edge of a lake that feeds into a river, with an island slightly to the West. It appears to have mostly wooden buildings of seemingly Nordic style, generally around 2 stories high, and in the concept art, there are 15 buildings at least partially visible. It contains a section that appears to have the Fall Forest directly surrounding it, so doesn't appear to be walled in. There is also a section built on stilts sticking out of the water and another section at the water's edge that does not seem to be on stilts and contains a port. There is a fishery with smokers, a hatchery, an advlt pond and gutting tables. At one point at least, there was a place in Riften where joining the theives guild was possible. http://www.uesp.net/wiki/Lore:Rifton
Windhelm
Windhelm is in the hold of Eastmarch, in a snowy region. Windhelm is the largest city. It has a palace that should look spectacular. This is also apparently the hangout for the Imperial Guards who monitor the path to Morrowind (From one of the Foreign language mags, I forget). The latest map suggests rebels are based here (Though this seems to be contradictory to the idea that it is the hangout for Imperial guards). Windhelm was once the capitol of the First Empire, the old palace of the Ysgramor dynasty can still be seen in the center of the city. The palace is in fact one of the few original First Empire buildings left, as the city has been sacked twice, during the War of Succession (before 1E 420) and by the Akaviri army of Ada'Soon Dir-Kamal. http://www.uesp.net/wiki/Lore:Windhelm
This may be Windhelm. The environment and location seems to match the map. http://img16.imageshack.us/img16/7418/skyrim2.jpg
Solitude
Solitude is a city in an as-of-yet unnamed hold in Northwestern Skyrim, bordering regions of Tundra Marsh and Pine Forest, and borders the ocean. In the northern parts of Solitude is the Bard's College. The city is a busy port and there's event similar to bonfire night that has the burning of an effigy of King Olaf. It is famous as the Northernmost point in Tamriel. Solitude was once known as Haafingar, which suggests a possible Dwemer origin. Going by the latest map, this is where the those on the Empire's side of the war are based.
It is likely, given the location environment, that this is Solitude. http://i.imgur.com/G4aLM.jpg which may be a later version of this concept art http://www.thedragonborn.com/wp-content/uploads/2011/01/concept1.png though I think this is unlikely, as the environment is different and the building style is very different. Though it does retain the rock bridge over inlet idea.
Whiterun
http://cdn.zenimax.com/akqacms/files/tes/concept_art/WhiterunCityTundra.jpg
Whiterun is a city in Central Skyrim, in the Hold of Whiterun, in a Tundra region. The area containing Whiterun and High Hrothgar used to be referred to as the "Imperial City of Skyrim", before it underwent several acts of choas, including a dynastic feud, attacks by H?rme bandits and frost trolls, and a series of annihilating winters of alternating floods, droughts, and fires. A self-proclaimed priestess of Lorkhan, Jsashe the Witch-Queen, controlled the county and the local witches' coven at the time "A pocket guide to the Empire" was written. http://www.uesp.net/wiki/Lore:Whiterun
I suspect the city at sunset/rise in this image may be Whiterun. http://i767.photobucket.com/albums/xx316/randomguyface/Variousshots.png?t=1296069496
I also believe this may be part of Whiterun, and the big building is perhaps the castle (we can see from the Markarth castle that they are not generic like Oblvion). http://img576.imageshack.us/img576/1102/skyrim3.jpg
Smaller Cities and Towns
There are 20 minor settlements in Skyrim, each of which is said to have at least 10 houses. There are 3 places listed as cities on the old map that are no longer part of the "massive" 5. It is unknown whether these will be made as smaller cities or large towns or what. Here are some cities and towns likely to be in. The only one confirmed is Riverwood.
Dawnstar
Dawnstar is a garrison town on the northern coast of Skyrim. It was after the destruction of a fortress in Dawnstar during 2E 283 that Potentate Versidue-Shaie declared martial law, leading to one of the most brutal and bloody periods in the history of Tamriel. At the end of the third era, Dawnstar's Queen Macalla married Thian, king of Solitude leading to an alliance between the two city-states, as part of an expansion of Solitude's power in northern Skyrim.http://www.uesp.net/wiki/Lore:Dawnstar
This is possibly some concept art of Dawnstar. http://www.thedragonborn.com/wp-content/uploads/2011/01/concept1.png The architecture is possibly of Dwemer origin, as it has some aspects of that, and another possibilty for the town's identity is Winterhold (see below) or perhaps Solitude.
Winterhold
Winterhold (sometimes called Winter Hold) is the capital of the namesake county and a coastal fortress, located on the northeastern tip of Skyrim. Somewhat isolated from the rest of Nord culture, but still wealthy and influential, it is known as one of the Old Holds. Due to its proximity to Morrowind's border, Winterhold is heavily affected by Dunmer ways and ideas, fueling part of its economy. It contains the Ysmir Collective, and the well-known College of Winterhold. The ruins of Saarthal are closeby. The failure to appoint Jarl Hanse of Winterhold to King of Skyrim ignited the War of Succession in 1E 369. http://www.uesp.net/wiki/Lore:Winterhold
Falkreath
Falkreath is a town in south-western Skyrim, close to the border with both Cyrodiil and Hammerfell. Just across the border in Hammerfell lies the town of Elinhir. At one point the city seems to have been counted as part of Cyrodiil. In the first and second eras, Falkreath was one of several kingdoms making up western Colovia, but in the final century of the second era, the kingdom came to greater prominence under the leadership of Cuhlecain and his general, Hjalti Early-Beard or Talos - later to be known as Tiber Septim. http://www.uesp.net/wiki/Lore:Falkreath
Riverwood
A small logging community in a Pine forest region near High Hrothgar. It has a 'spattering'of houses made out of wood with straw roofs and has a pub and a smith. There is a mill, seemingly powered by a water wheel. The town can be seen here. http://img641.imageshack.us/img641/174/skyrim7.jpg
Granitehall
Sunguard
Kynesgrove
Oakwood
Dunstad Gove
Stonehill
Dragon Bridge
Laintar Dale
Northkeep
Green Wood
Karthwasten
Other Locations
There are roughly 120 dungeons in the game, including Nordic Ruins, Ice caves and most likely Dwemer Ruins.
Bleak Falls Barrows
Bleak Falls Barrows is a dungeon, with ancient Nord catacombs which features rivers, tree roots coming through the ceiling and light coming through odd cracks. I suspect that this concept art is for Bleak Falls Barrows. http://www.thedragonborn.com/wp-content/uploads/2011/01/nordicruins.jpg-610x0.jpg Also, this could be the entrance (It is described as the entrance to a Nordic Barrow. http://cdn.zenimax.com/akqacms/files/tes/concept_art/NordicBarrowBruin.jpg
High Hrothgar
High Hrothgar is a settlement high atop the highest peak in Skyrim, the Throat of the World. Sitting atop seven thousand stone steps, here dwell the ancient Greybeards who endeavor to become more attuned to the voice of the sky. The Nords believe that they were created by Kyne when the sky breathed onto the peak of the mountain, which is also known as Snow-Throat or the Throat of the World. It is possible that Hrothgar has a mystical connection with the vanished Falmer. While this is probably not the precise one, there may be a temple at the top of High Hrothgar similar in appearance to this. http://www.thedragonborn.com/wp-content/uploads/2011/01/nordictemple.jpg-610x0.jpg
The mountain on the left in this image, towering above the others, is likely to be High Hrothgar. http://www.gamestar.de/_misc/images/original.cfm?pk=2198717
Sky Haven Temple
An old Blades Temple. It contains Alduins Wall, a prophetic carving that shows the events leading up to the consumption of the world by Alduin. I suspect that the building on the left in this picture is Sky Haven Temple. http://i767.photobucket.com/albums/xx316/randomguyface/Variousshots.png?t=1296069496
Another possible appearance of part of the temple is in this image. http://www.gamereactor.no/media/59/elderscrolls5_235971b.jpg
So yeah, I'll add more or fix things up if you guys have any other info.