The basic design of armies and agents since Rome 2 - for better or worse - is that they are less numerous and more individually important. Sending an army to one side of your empire means - unlike in, say, Shogun 2 - you are deciding to not have a unit on the other side. Positioning is very important, for better or worse, and it's always a good idea to have each army and agent doing some thing useful or heading to somewhere where they'll be more useful.
The downside of this is that you end up kind of close to your own borders for a long time, especially in Warhammer where there are no naval units (for better or worse) that might be doing some scouting in other Total War titles. Agents are a little hard to come by, and again limited in number, so they're not really what you want for scouting either. Overall it really feels like there's no good way to get a good sense for what's going on around the world. You have your corner of the world, they have there's, and you dare not leave it for fear of being too far away to deal with a sudden enemy invasion.
My suggestion is a very simple scouting ship which sort of operates like an automated probe. It's not a naval unit that can participate in battles, nor is it an agent that can harass the enemy or whathaveyou. Perhaps it might be able to explore ruins and islands, but I think that's not what my intended purpose for it is. It should, at the end of the day, be a scout - pure and simple - and one with a limited lifespan. You pay about 500 gold to make this ship at a port, and maybe it can go about 5 or so turns before it 'returns' from its 'expedition', with tales of new lands and new peoples.
The end result is that something like the Empire in the Old World can more comfortably meet up with, say, the High Elves or the Lizardmen - which it normally wouldn't know about at all unless you wanted to be very reckless with your armies. The fact that its lifespan is limited prevents it being effectively an immortal spy you can plop somewhere, and it would in general operate much like historical merchant and exploration expeditions did in the Age of Discovery. You're sending a caravel to open up your markets to new regions and new goods, not sending a military fleet or anything to conquer a place you've never heard of. That's what you're kinda forced to do now, which makes no sense. You'd need a scout before you send an invasion force. Columbus before the Conquistadors.
I know I've mentioned changes in the franchise as being 'for better or worse' a few times, and while I may be a grumbling old Rome 1 vet, I do think that if CA changes one thing because it decides that such is a good idea (like say, fewer armies or no naval fleets) then they have to change something else to balance the scales and make up for what may have been lost by that design decision. It is a balancing act, and I think a very barebones exploration vessel for each faction would be fine in this regard.