I went through this same debate/dilemma last summer. I chose to go with a sub-domain (example.com/mobile). My reasoning was that I felt mobile content was simply a display variation of my main content, just like a print version of my pages. That said, I felt it should not be on another domain (or subdomain). It belongs on the main domain (in my opinion). Sub-domains are for content that is distantly related to your main domain. Mobile content is the same content, so I didn't consider it "distant" enough. =)
So after I decided on that, I did some reading up on duplicate content. I ended up going with the canonical tags on my mobile pages to designate my main pages as the "real page" and the mobile version is just that, a display variation of the main page. I had read somewhere on Google help pages that they recommended using canonical tags for print pages, mobile pages, etc. That was enough for me to go in this direction. I've read of other webmasters who skipped this step (canonical tags) and it worked just fine as well. I am doing a test right now with the canonical tags removed in an attempt to remedy a problem I'm having. My mobile pages don't seem to show up in mobile searches (my desktop pages do), and I think it might be related to my canonical tags. We'll see if removing the tags fixes that problem.
For formatting, I used XHTML. That alone is also a sign to G that your page is a mobile page. I also submitted a mobile sitemap to G.
After all this, I setup a redirect based on user-agent in my apache configuration for known mobile agents.
My site is 10 years old and my rankings didn't seem to have been negatively affected by this design. I launched in July (about 6 months ago). Granted there have been lots of roller coaster changes G made to SERPS and their ranking algorithm over the last 6 months, but my mobile traffic seems to be steadily growing, and now I'm focused on trying to better monetize my mobile traffic. Which is another beast in its own. =)