I want parts of my site to be accessible to Android, iPhone and other mobile platforms. Is there a particular theme I should start with, or anything I should look for in a theme besides it being clean and simple? Would I be better off creating a theme from scratch?
The Omega theme is a grid based theme that will allow the developer to use a shared CSS file and three different CSS files for different screen resolutions. This way the same site can be served to different devices without having to do a ton of work to make it look nice on all of them.
Honestly, iPhone and Android devices don't need special mobile sites, they just need a bit of thought put into the layout, and that was what I assume you're after judging from your question.
If you really want a specific theme for mobile devices then I'd recommend just starting with one of the many Drupal base themes, and trying to keep it simple. Keep it 1 column, avoid
position:fixed like the plague because the iPhone doesn't do it. Avoid
:hover wherever you can for the same reason.
These sites that are designed to look like apps are more often than not annoying, especially if mobile devices are automatically redirected. You'd be much better off directing your time into something like Responsive Web Design, so your mobile visitors get the same content with a better layout.
Definitely agree with Paul Jones, these mobile devices don't need special mobile sites. I think that your website and all your content should be available as well on mobile devices as on desktop. It also seems a lot of overhead, creating and maintaining seperate themes.
A better solution would be an adaptive theme that doesn't scale to specific devices like some modules or themes do, but that adapts to screen sizes, with things like media queries, flexible grids and flexible layouts.
I would also suggest checking out jQuery Mobile UI which is developed by Jason Savio. I attended his session at the Design 4 Drupal Boston 2011 and it definitely looks very promising. Apart from that, I dont see any other native jQuery Mobile module for Drupal 6.