15-20 year old truck, not sure how many years you expected to get out of tires. Yes michilubes seem to dry rot more/quicker than some, but in your case I wouldn't look for the best tires, I'd look for the cheapest tires if they're going to rot out before they wear out.
On a budget, check Craigslist or as Amazon. May find some takeoffs on CL but 16s have gone by the wayside, about 15 years ago.
Another option is buy a new set of takeoff 17/18/20s (they'll all fit under a 2nd gen 4x4, if you have 2wd stay with 265-70-17 as the biggest). There are piles of new Ram takeoff wheels and tires for less than $1000 around here. Plus you get the advantage of ditching the old 16s.
If buying just tires, you can find a bunch on Amazon LT245 or 265 for $100-150 a piece shipped.