I'm also looking for a hike for veterans' Day weekend- though preferably in the central four corners area. And, lo and behold, I find your post!
I'm thinking about revisiting Great Sand Dunes NP. It's easy to get to with a rental car, though the drive is long compared to most fly-in-and-rent-a-car hikes. It's a beautiful place, but in a way very different from other national parks. It backs on the Sangre de Cristo Wilderness, and several trails lead into the wilderness from the park, so if the weather cooperates you can still head into the mountains.
Any other suggestions are welcome. I live in Colorado Springs, so almost all of the four corners area is in easy driving distance. I remember several posts on this forum about canyon country in Utah this time of year, and any ideas along those lines are very welcome. I'd like to avoid slushy weather, but merely cold is fine, and dry snow that isn't deep enough to posthole is fine. (I have no skis or snowshoes.) I'm also thinking of avoiding higher elevations, as weather this time of year is unpredictable.