How large does the area need to be, are you traveling four days across it, two weeks? A month? I'm not sure I can provide a good answer for a very large desert, but in my travels I have found a small desert (that used to be much larger) in Southern Manitoba. (Latitude = 49.666)
It is called the Spirit Sands. It used to cover an area of 6,500 km, now is about 4 km across and took 5 hours to hike on a brisk September morning. 6 am was around -2 (cel) and 10 am was around 8/10 (cel). The surrounding geology is an area known as The Canadian Shield, a large rock mass. It is very diverse terrain, tons of quartz, and as well mostly boreal forest. This boreal forest extends thousands of kilometers north and east, it gives way to the (flat) prairies to the west. Edit And the Rockies are further west past that.
It was a large river basin that slowly drained giving way to the shifting sands there are there, I think some of what may have given rise to this is further north the land becomes tundra (and permafrost area) and well used to be covered by glaciers. The glacial deposits ran further east as the land experiences greater chances in elevation. The Red River to the east, and near Winnipeg floods seasonally.
This picture is just before the rise to go into the larger desert.