We're currently working on a project for Global Stories which requires a fairly complex map interface. We've been looking into alternates to Google Maps, as we'd like to find something which gives us a bit more control over the look and feel and the interaction within the map.
So far we've been exploring the following mapping services:
A downloadable mapping applicaiton by Tile Box. It makes use of Carto stylesheets for customising the look and feel of the map and can be output for usage on the web.
CloudMate provides a point and click interface for customising the look and feel of their map. The styles are stored online and can be loaded into 3rd party applications via their API.
Styled Google Maps
Google provide a stylised version of their maps via their styled maps wizard, the colours and visibility of all elements can be altered dynamically at runtime through the Google Maps JS API v3.
Our current favourite is PolyMaps, which looks to have been implemented nicely using SVG, has lots of ability to customise the look and feel and not to heavyweight. Check out some of the nice examples, like the tile visibility algorithm and the Flickr Where On Earth implementation.