Now that we've bought ourselves some breathing room and may just have a viable fleet running, our list of strategic options has expanded considerably. Let's account for our current list of priorities.
-Tywin needs to be checked as an existential political threat to our Regency. King Joffrey's safety needs to be guaranteed as quickly as possible - although it's a shame we weren't able to blood him with an easy win, the danger of our monarch getting snatched is simply too high.
--In the immediate term, cooperating with Edmure to kick dear old dad out of Harrenhal seems like a necessary step to solidify our alliance with the Tullys and the legitimacy of our political authority. After that, waiting for him to die is probably our best bet.
-Stannis and Renly are running around in the Stormlands, and both represent considerable risks. Stannis's magic access makes him a dangerous wildcard, while Renly still commands a lot of men despite his Tyrell alliance falling through.
--Thankfully, with the immediate Targ pretenders defeated, we've got a handy army to sort them out, one that will hopefully be bolstered with Reacher levies soon enough.
-The Vale is a mess. Thankfully, we've suddenly got ourselves a fleet, which makes having to bust through the Moon Gates no longer our only option of intervening!
--For now I think Lysa can sort out her own business, but once we've gotten some breathing room, landing an army in Gulltown would be a very poignant way to assert power in the region and sort out another damn Targ pretender. Same thing with the other petty kings that're trying to strike it rich, although they'll no doubt be easier to handle.
-In the slightly longer term, I suspect the Golden Company will be visiting our shores soon enough, potentially backed by a betrayal from Varys (although who knows what game the Spider's truly playing).
--Right now the details are too vague to plan much out, but having a strong navy set up should provide a considerable deterrent. In the meantime, I'd get Rykker to work on sorting out piracy in the Narrow Sea to season our fresh crews and provide some relief to King's Landing.
-At this point, the danger has passed enough we might be able to focus on sorting out the Crown's finances.
--Littlefinger clearly hasn't won Lysa over, if he even tried in the first place, so it could be time to have the whoremonger replaced with a reputable Master of Coin who'll tell us how bad the situation is.
-As Azel so succinctly put, our alliance with the Tyrells is the only thing keeping Cersei in the game at the moment.
--There are several things we can do to get this partnership cooking, like finally appointing Garlan to Master of Laws or picking the Action to interface with Margery, but I suspect we might also want to give poor Mace some face, as his reputation has taken a bruising and it sounds like the Reach coast will soon be subject to Ironborn reaving.