Ahh, the MacPro 4,1 and 5,1 - models close to my heart. I loved these machines (I still have 2).
[edit - my link was deleted for reasons I cannot discern - I suggest doing a google search for "Definitive Classic Mac Pro Upgrade"]
In general a SSD upgrade with breath new life into a machine. I did this myself, although I have to think about how I migrated data...... IIRC, you want the boot drive and programs on the SSD, while bulk data is on the the older spinners. I think I did a split Migration Assistant from the original drives, although the details escape me.
For the later OS you need a specific type of video card ("Metal"). I ended up getting a 8 GB/RX580 which fit within the power requirements and was usable (although it didnt have a boot screen).
Go with SSD first. More RAM second. If you feel brave, I recommend doing a CPU upgrade as you can get top of the line CPUs for that machine for cheap (I did this twice), but you will get your hands dirty (I used a micro blowtorch for my rev. 4,1, and spend some tooth grinding moment getting the heatsinks properly centered.
Ultimately you can take these machines pretty far if you want to look behind the curtain (Open Core).
Tom
[Edited by Moderator]