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.
I agree. Mormons seem to be pretty aware of their outsider status and like to stay in the mainstream in order to win over skeptics. However evangelical Christians, especially in the south, firmly believe that their faith is the right faith. If anybody accuses them of being outdated, then it's everyone else who has the problem. They'll dig their heels in when it comes to gay marriage unless a federal or state law forces them to deal with it.
So I'd say Utah legalizes it before a state like Alabama or Tennessee. However, they're all far from it.