Yes, to be sure your email will work across a reasonable range of email clients, you do need tables, unfortunately. It's amazing that this area is lagging so far behind web standards, but with companies like Microsoft basing Outlook around the Word rendering engine, there isn't much hope for things improving for a long time yet.
The safest way to add CSS to an HTML email is to place the styles inline—again, a real pain. Some email clients still strip out any styles contained in the <head> section, so it's not as reliable.
The ideal would be to code emails with web standards only. If we all did that, companies that provide crap email clients would go out of business, because people would stop using them. In reality, though, this never happens. (And it would basically mean everyne would have to use Mac Mail! :lol: )