but what version should we be considering
Always the latest LTS a couple of months after that LTS got released. Let other people iron out bugs for you before you upgrade a production server.
and what challenges might we face going from 12.04 to newer supported version(s)?
The Ubuntu server versions do not tend to need more power the newer the version. Specs have been fairly the same so not a lot going to be a problem there.
Always check your video card and NIC chipset against the drivers supplied. Old graphics card support gets dropped every new LTS in case you have one. NIC chipsets do not get dropped that often but you never know.
There is 1 very big change: systemd
got introduced and it is a beast: it completely changed the boot process and how services are taken care off. And that can be the biggest challenge if you use custom upstart
files for services. You will need to re-code those.
All other changes are minor (as in regular updates and improvements).
And always make sure you have backups that are correct and you know how to restore.
As a precaution: use a new machine to create the new OS and then use a backup to restore your personal files. Often a lot easier to manage and it removes the downtime of the upgrade of the old machine.