I am someone who also agrees the rival system needs tweaking as it makes some games lost causes before you unpause. (though it was "Recommended for New Players" Castile/Portugal getting roflstomped by a France/Aragon alliance three games out of four in my case)
Still, there are a couple of things you can do to up your odds, some depending on DLC.
First, have you ever considered Brandenburg as an ally for that first TO war? as long as you start it before the sale of Newark triggers for them, they should be positively thrilled at you offering it to them as payment for joining up. Obviously you're almost certainly going to have to dump them at some point for better allies (especially if they try to drag you into fighting half the major HRE states to take Silesia), but for a quick reliable ally, they're pretty good.
Second, if you have Art of War and Cossacks, Lithuania doesn't have to be a sketchy ally. With Art of War, you can set their military focus to either Supportive to stick close to you (often in a one-province-away-to-lure-armies way too) Siege to stick to taking proviences while you hunt down armies, or Defensive to hunt down armies while you siege. With Cossacks, your subjects will fabricate claims on any neighbor you are hostile or rivaled to, and you can set hostility on your own regardless of the current mutual opinion, so setting LO to hostile should encourage Lithuania to fabricate the claims you need to go to war with them should TO ally Denmark or another nearby nation you don't want to fight yet.
Finally, if Austria, Hungary and/or Bohemia are giving you the middle finger, consider looking a bit further for allies to protect against any possible Muscovy/Ottoman Alliance. If Austria rivaled you, France will almost certainly be willing to ally, and barring *really* horrible luck with taking back their cores from England, should be strong enough to scare most alliances, and is unlikely to be weakened to the point where they'd bail on you either.