First off the factory air inlet/airbox IS a Cold Air Intake (it is fed from cold air in the passenger fender.) Second, there's no noticeable power gains from any off-the shelf CAI worth mentioning; it's mostly done for sound more than anything else.
Your mileage is going to suffer with larger tires, these are BoF SUVs, pretty much any modifications will just tick away at the mileage. Depending on how big the tires are, you could re-gear the differentials, but realistically you're probably going to be around the mid to high teens if you're modifying these vehicles. (Hell I'm getting 11mpg these days on average since I barely drive more than 5 miles a day and the truck is barely warmed up by the time I get to work; I get around 14~15mpg with crappy California Ethanol fuel; 16~17mpg running non-Ethanol fuel when I went to Oregon.)
If fuel mileage is that big a concern you unfortunately purchased the wrong vehicle, you might be better off investing in a commuter (and dedicating this as your fun-time vehicle) if that's an option because it's just not realistic to expect good fuel mileage from modifying an SUV for off-road use.