If you want the modern Gaelic names for cities in Scotland and Ireland, check out this place:
Tìr Chaluim Chille
If you want medieval names, I can provide many (for Scotland at least).
For Scotland today, cities such as Glasgow and Edinburgh are the largest, and therefore most important; but they were not as important for the Gaelic period, and in fact were on the fringes of the Gaelic world. In the medieval period about 80% of people in Scotland lived north of the Forth. But anyways, here are lists of modern Gaelic names for important medieval places. They are roughly in order of importance (IMHO), separated into places with cathedrals, royal centers (usually castles or ceremonial sites) and just general cultural sites (there is a general absence of places in Lothian, an area [like the northern isles] that was never really Gaelic):
BISHOPRICS
Dùn Chailleann, (Dunkeld, Bishopric of Athall [=Atholl])
Cill Rìmhinn (St Andrews, Bishopric of Fìobh [=Fife])
Taigh Mhàrtainn (Whithorn, Bishopric of Gall Ghàidhealaibh [=Galloway])
Glaschu (Glasgow, Bishopric of Srath Chluid [=Strathclyde])
Breichin (Brechin, Bishop of Aonghais [=Angus])
Dùn Bhlàthain (Dunblane, Bishop of Srath Èireann [=Srathearn])
Obar Dheathain (Aberdeen, Bishop of Màrr [=Marr])
Eilginn (Elgin, Bishopric of Moireibh [=Moray])
Dòrnach (Dornochm Bishopric of Gallaibh [=Caithness])
Ros Maircnidh [Rosmarkie, or A’Chananaich (= Fortrose;, the two are just next to each other)] (Bishopric of Ros [Ross])
Lios Mòr (Lismore, Bishopric of Earra Ghàidheal [=Argyll])
Also, if it counts,
Purt ny h-Inshey (Bishopric of Sodor/Innse Gall/Mann)
ROYAL CENTERS
Sgàinn (Scone)
Dùn Phàrlain (Dunfermline)
Peairt (Perth)
Dùn Fhothair (Dunnottar)
Dùn Èideann (Edinburgh)
Tòrr an Dùin (Burghead)
Sruighlea (Stirling)
Fothair Tabhaicht (Forteviot)
Dùn Dèagh (also Baile Ailleag = Dundee)
Inbhir Àir (Ayr)
Dùn Breatann (Dumbarton)
Inbhir Pheofharan (Dingwall)
Inbhir Nis (Inverness)
Dùn Dùirn (Dundurn)
Dùn Phris (Dumfries)
CULTURAL CENTERS
A' Chomraich (Applecross)
Obair Neithich (Abernethy)
Baile Ghobhainn (Govan)
Cuileann Ros (Culross)
Pàislig (Paisley)
Obair Bhrothaig (Arbroath)
Dùn Droighnein (Dundrennan)
Port Mo Cholmaig (Portmahomack)
Loch Lìobhann (Loch Leven)
Deir (Deer)
Cill Tighearna (Kiltearn)
Beannchar (Banchory)