Oklahoma or Alabama no doubt.
As several have pointed out, mormons might be solidly Republican, (and I know prop 8 and stuff) but they're more educated than their evangilical brothers, and they like to not be too out of the mainstream. So Utah, WY, or Idaho will not be last.
This; there's already a small but growing group of Mormons pushing for gay rights (mostly nondiscrimination policies, but many want civil unions, and a few are even okay with same-sex marriage).
And don't forget that the largest city in the state is very gay-friendly and has been so for a decade.
Wyoming might actually be soon-ish, I hear, since there seems to be a libertarian trend over there.
