I like to encourage my horse in the beginning of the ride to really stretch his neck down and put his nose on the ground. It allows him to stretch his back out. He is usually stiff when I first get him out so giving him a long time to walk before any work. It helps when you do start work to get up off their back to let them loosen up a bit then lots of lateral work.
You can work your horse before riding by doing some stretching exercises! He will use his muscles without a weight on his back, which is nice. And when you are on his back, do a lot of circles and bending.
Driving reins is a great idea! To me, flexions in walk are the best exercise you can do to soften your horse! But be patient, at first, it can be hard for your horse to do flexions. Work a lot on lateral movements and bending!
You can work with driving reins, it really helps! And do a lot of circles (large ones then small ones), flexions in walk and trot (keep in mind the horse's nose has to almost touch your feet), lateral movements... Be patient! If your horse is really really really inflexible, you can lunge him with an overcheck, it will help him to relax