Impressive, breathtaking, really awesome... Feel free to add as many 'wow' words here : they would be all true ^^
I say yes to red labels : they would make the map really pop. Maybe a little red detail on the towns landmarks as well... but this would need some experiments first.