I have a 'responsive theme' on my Magento 1.9.1 store but it's not good enough...What is the best way to setup for mobile devices (tablets, mobile phones) so that both the customers and Google be happy?
You can use design exceptions to switch out the theme for your store based on the user agent of the client browser. This will allow you to switch out the theme but it won't allow you to configure the stores differently.
If you need more flexibility then you will need to set up a new magento store for your mobile site. This way you can change the theme, URLs maybe and any other config you need different on your mobile view. You would need to implement some logic to switch between the store views based on the client browser, magento doesn't do this out of the box.
Design exception will do the magic. http://www.implementek.com/11392/#.VaiCR5MX5hg Refer this link.