The scale may be a bit different but a Victorian look for my neck of the woods:

A couple more links (to Caledonian Maps) as well:
http://www.caledonianmaps.co.uk/edinburgh.gif
http://www.caledonianmaps.co.uk/edinburgh_mid.jpg
http://www.caledonianmaps.co.uk/OS_zoom_zoom.gif

John Tallis' maps of the time (mid 19th Century) are also very nice and may be up your street if you fancy ornamenting the periphery with a few pictorial representations of key monuments/buildings.

I like the steampunk+magic mix to the world and am minded of Harry Turtledove's The Case Of The Toxic Spell Dumpin which the favoured mode of transport was the flying carpet.