If you have your own exchange server, don't let them sell you on any bull**** that you need some special data plan in order to access it. I'd say just get whatever unlimited data plan is cheapest (along with any other features you want like text, etc.).
I don't have a stock ROM on my phone, but I thought they also come with Live Search built in now. If so, nobody will have to spend any time or money updating phones. It might not be quite as simple for a navigation solution as Telenav, but it is free and built in. Plus it has lots of extras like gas prices, local search, etc.
Edit: looks like you were posting as I wrote that. Sounds like you're ready for that phone conference
