We also had this problem developing joobili.com
Honestly it was not easy, but I think the solution we have now is good.
We don't serve different content to search engines, because that is called cloaking, and google does not like it.
For every page we have an html version (honestly that is not a big deal, you don't have to deal with design at all, just put some content and links on the page).
You can use the tag for displaying this content. You can also speed up thing a bit, if you provide the initial content also in object form on the page. For that we use a slightly modified version of the kiyaa frameworks object serializer.
We also use gwt 2.0-s codesplitting mechanism, and this makes the loading of the homepage a lot faster.
Of course you have to make sure that the content you provide for the search engines (browsers without javascript) correlates to the one you provide to users.
Best - Istvan - inepex.com