"hoping to avoid main highways as much as possible and enjoy some of the side country roads" I'm laughing, because even our #1 highway is a "side road" compared to many US interstates.
If you look at a map that has geological features, it is easier to spot where the Prairies end... between Calgary and Banff if you are in the south, and around Hinton if you are up north near Edmonton.
You will not find a lot of "dispersed" aka "free" camping in Canada. BC seems to have more of that though, so check out the book "Camp Free in BC". Also the BackRoads Guidebook series is good too.
If you want slightly better scenery across the Prairies, consider taking hwy 16 out of Winnipeg to get to Edmonton and from there on to Jasper. The #1 is shorter/faster and deadly boring, in my opinion. We used to drive that Winnipeg to Vancouver annually to visit family. The 'Peg to Calgary run is 13 hours of driving at speed limit, and the Mounties are active on that road.
Once in Calgary you are just 90 minutes away from the Rockies. Highly recommend checking out Kananaskis Country - Where Locals Hike. There are Provincial Parks in K-Country and campsites that take reservations, and also some first come first served sites that we tend to favour. West Spray Lakes is a nice camping area... but be warned that Calgarians FILL these campsites by Thursday noon, so arrive before that if you are around on a weekend.
DO drive the Icefields Parkway, with this book - Don't Waste you time in the Canadian Rockies - in hand. We've had good luck getting into the Wilcox Campground some weekends... it is cold (altitude and closeness to the Icefields) and has short/sharp corners so no trailers are getting in there.
I'm hoping a few others will hop onto this thread to add more info...