I was just wondering this last night before going to bed. Obviously any state with islands would be problematic (Alaska), any state composed ENTIRELY of islands (Hawaii), and any non-contiguous state (Michigan) would be out. My state of Oregon would be pretty cool for the coastline, but the straight California/Nevada border and then up the Snake River and down the Columbia are not great routes. My pick would be the great state of West Virginia:

Which State's Outline Would Make the Best Track?

West Virginia is noted for its mountains and diverse topography..

That's from the very first line on their official state website! Seems pretty perfect to me.

What state would you pick?