Somewhere in the Deep South. An interesting counter one is which GOP is most moderate. I would probably say Vermont, Massachusetts, and perhaps Maryland. Maybe California, certainly Arnold Schwarznegger was quite moderate compared to much of the party but Pete Wilson was fairly right wing so not sure if they've swung rightward since. Mind you the GOP is increasingly becoming an endangered species in California.
Out of those you mentioned, i'd say Vermont for the most moderate. Phil Scott as a example is by all means in favor of mostly socially liberal policy's (for a republican), is mostly 'ok' with legislatively legalizing Marijuana, supported the Recovery act, and (again as a republican) supports expanded healthcare insurance. Mass, Conn, and also Maryland as you mentioned are up their also. Though California as you eluded too is far from the 'liberalness" of the state party's already mentioned.
As to the OP, i'd say states like Alabama, Oklahoma, and Kansas top the list.