Having to move your capital, and the trouble, time, and expense of doing it, is part of the penalty of losing your capital in the first place. The game will not elect one for you.
Where did I suggest that there be no penalty? Having the game pick a place for you could very well be a penalty in it self. Of course, I would never suggest that the game say "BattleMaster Has decided that your new capital is City2 as you never decided yourself." It would say something along the lines of "Having received no direction from the ruling council, officials, clerks and minor nobility have begun congregating in City2 and the people hail this place as the new capital of Realm1"
Additionally, I am suggesting that the monetary cost be optionally replaced with other costs. I really do not know all the details of capital moves but I imagine it like this:
Capital leaves.
The ruler is asked to pay XXX gold and pick a new city to make the capital
If they do:
They determine where their capital is
The capital takes X days to be established
Realm stats receive x hurt
All the normal, whatever that is
If X days pass ant they do not pay up:
They do not determine where the new capital is - This could result in sub-optimal locations
The capital takes XX days to establish (longer than otherwise)
The realm receives XX hurt (more than if they had paid up)
The beginning of establishment was started way later than if they had paid up right away.
I do not see how any of this is suggesting a lack of penalty and I do not see the problem of random selection. It is not taking anything away from players. It is simply preventing realms that lose their capital due to allegiance changes (or successions) from having no chance at all of establishing a new capital. It is but one of many possible ways to make capitals leaving realms possible. If something is not put into place to address the "Crap, the capital left us and we can not afford to establish a new one" problem, I would think that simply preventing capitals from leaving at all would be best.
You all do what you like though. Leave it as is, find a solution more to your liking. Whatever.