Never done a table layout myself. But I've had to clean up some nasty table-based layouts before and that wasn't funnyNever done a CSS layout, but is the whole point to reduce time in both development and download?
I agree. The challenge is to design the html in a way that it is the most logical, semantic and lean. So that even without css the pages "work". That's good for users, search engines and ease of maintainance (future layout changes etc). I am just redesigning one of my sites and after changing maybe 10-20 lines in the main stylesheet the basic changes were done. Not having to touch the html-templates makes the job so much easier.For starters, its two different jobs, and it requires two different tools. Using photoshop and imageready, converting images into workable html is one job. Taking html and making it compliant is another - a much easier one
About the xhtml vs html difference: I don't think there's an advantage of using one above the other. as long as you use a strict doctype and validate the pages you're fine. It will take IE years and years to support xhtml, so as long as the majority of people use IE there's no point in using xhtml (but that's a whole different discussion..)
So I think the most important thing is is to find someone who can really convert your designs to solid, lean and meaningfull html. It might cost some more in the beginning (compared to a quick and dirty job in frontpage/dreamweaver hacking together some images and layers), but in the end you'll have pages that work better, are cheaper in maintainance and are good seo wise.
To try to answer your questions:
The cost will depend on the complexity of the design. A basic 2 col layout is much easier then a complex grid of block different sizes etc. But as I said, a good job will save money in the future, while a quick hack might cost more in the end.
I don't think it would be cheaper to first write the html yourself and let it be converted to xhtml. In contrast, for me it would only make it more difficult. Starting from scratch is easier.
Making sure the pages validate should not be difficult for anyone claiming to be an expert/having experience. Validating is just a usefull tool to find some silly mistakes I made writing the code (forgetting some end tag f.e.).
Hourly rates: that's difficult to say. Here in the Netherlands it will be somewere between 20-100 euro. Depending on who you pick, the neighbours friend's 14 yr nephew or some corporation's front-developer.
As for the next question: changing a single html file to xhtml? Maybe 10 minutes. Maybe a few hours. I would have to see some code before I could know that. Nested tables aren't the problem. It's how well hidden the real content is and finding that
And the biggest advantage of changing it to a css based layout is that maybe the first and second page and the css will take more time, but after that it's way faster and easier.