Aye, although don't forget about Open Street Maps... you have more of the world available,
you can download relatively compressed maps just like Nokia Maps, and you can implement some sort of routing, although I'm not sure how evolved that bit is.
Oh, did I mention that it's all free? :-) Dev would be expensive though - routing implementation, OSM format handling and so forth. You basically need to create a maps application*, just like Nokia's.