Ubers: for that Palk set, I'd go with Aqua Tail, since you do run into Blissey on occasion. Outside of Gira, none of those movesets will do much to it. My Modest Scarf Kyogre can barely OHKO Blissey with Spout as is.
Another problem I see with that Palk set is Chomp usage. It won't be able to come in at all unless Chomp is asleep or Outrage Confused.
Honestly, it's hard to say how the addition of Hydro Pump for Palkia will impact the metagame. I know that Giratina will see more use, since you frequently see Mewtwo, Giratina, and Wobb, among others. Dialga will almost certainly be packing Metal Burst to revenge kill ScarfChomp. Palkia users might opt for Hydro Pump over Surf if they have rain support. I can't see it happening since there's no accuracy boost to Pump in Rain.
If the Arceus obtained via the Azure is legal (which I think isn't) the ExtremeKiller set is the deadliest set out there and always considered when constructing an uber team. Which Pokemon do you think can counter this set apart from the ones listed in the strategy Pokedex. IMO, Jolly Life Orb Lucario, is the best counter to this set with Stealth Rock taken into account. Why Jolly Lucario? Stealth Rock Resistance, Close Combat, does more damage to Arceus than Groudon in one turn, can save team from being wiped out, type advantage.
No Uber has ever been able to counter ExtremeKill Arceus since none can take hits from Swords Dance Life Orb Extreme Speed with Stealth Rock taken into account.
I saw this after my post, so I'll add to my response. At present, Azure Arceus still won't be legal unless Nintendo decides to distribute the item on WiFi/Mystery Gift. For the movie Arceus, the nature and IV's would likely be a problem, but that depends on whether you can soft reset for them. The moveset isn't because of TM's and the Move Relearner.
I'm also interested to see how the unbanning of Arceus affects Shoddy. I've played WiFi matches against Arceus (some against the n00bs on Gamefaqs who broke Species Clause and used more than 1), and he's quite annoying. Normal Arceus is bulky enough to survive an Aura Sphere from Timid Mewtwo after 2 CM's.
For ExtremeKill Arceus, the best way to live against it is to stop it from SD'ing. Assuming no SR: when it comes in, switch to a Taunter or a Sleeper (Mewtwo or Darkrai come to mind) - at the moment, I'm not sure if Darkrai can survive Extreme after an SD, but Mewtwo can.