There used to be a limit of 101KB for Google, but that's no longer the case so size doesn't matter :-)
I mostly use Almost Spring http://www.morearnings.com/2006/08/30/wordpress-theme-almost-spring-with-google-adsense/
And Blix http://www.morearnings.com/2006/08/13/wordpress-theme-blix-with-google-adsense/
they both have right menus with the code for the menu below main content (that's why I use them).
Both links above are to the versions I use, they include AdSense ads as well.
I must create some SEO only versions!!
Got about 500 downloads of themes from that site this month so far and the pages aren't really ranking that great for relevant SERPs , so looks like a lot of people want SEO'd WordPress templates!