Nevada? Quite libertarian-voting in recent elections.

I'm not sure about the density, but you'll definitively find some appreciators and libertarians in New Hampshire - considering the Free State Project.

At the very least, I would look at states that elect self professed followers to Congress.