I've been wondering about putting together a new, utterly unthematic Melee deck, based around the new Robert (Grand Melee) Focused Offense, and True Power.

The premise is pretty simple. Robert attacks alone in a claim-3 Power challenge, and True Power makes sure it gets through. Could fairly easily get you around 10 Power.

Obviously, the problem is with Running Robert out of House (7 Gold) or Running the Alliance agenda, which gives everyone else a big power head-start (especially as you need a certain amount of Power on their house-cards to benefit from the challenges)

So, do people think there are enough other benefits to a Targaryen/Baratheon deck to make this build worthwhile?

Have you thought about doing it as a KOTHH deck? With the Alliance plot to play Robert, or just using your higher gold income. The slower start wouldn't be as big a burden because, as you say, you want each opponent to have at least 3 power on their house. And you could use some burn to slow them down and win challenges with Robert easier even if you don't draw True Power. The higher INI would let you go first more often too and grab the Crown Regent title for higher STR in the power challenge.

Hmm, or Heir to the Iron Throne with the Alliance plot and some ways to stand Robert?

My first thought was alliance plot as well.

Also, if you can get a maester with copper link out and a way to reliably kneel him (valyrian steel link would probably be a good choice) you could give Robert the Dragon trait, and run QoD Daenerys. You could do that with Heir to Iron Throne, or the plot that gives multiple power challenges. Heir to the Iron throne would be pretty ridiculous with a couple of 2 claim plots. In one turn, if you can get his ability off twice, you could get 14 power with a 2 claim plot [(2claim x 3copponents+1 renown) x2 challenges].