But wouldn't Allied V2-style missiles be just as crap hitting their targets as the OTL German ones were?
Yes. The Allies don't need V2s anyways, they have perfectly good heavy bombers. I'll get to this in a minute.
And even today, surely only ship-launched missiles are of the Cruise variety?
Ballistic missiles are only launched from submarines underwater, using pneumatics to push them above surface first - otherwise the rocket engines would destroy the ship.
(Or am I completely wrong there?)
Only partially wrong. The main reason the rockets aren't ignited underwater is because water is very very viscous and, well, they're rockets. Underwater. Those two don't really go together. There were plans to place Polaris missiles (the first American SLBMs) in surface ships, but those plans were never carried through for a variety of reasons, so they ended up limited to submarines.
There are also plenty of submarine-launched cruise missile designs, so the first part is rather confusing--you seem to be saying only surface vessels launch cruise missiles, which is patently untrue.
Anyways, the entire WI is basically ASB: von Braun has absolutely no reason whatsoever to emigrate to the US prior to WWII. He was doing just fine in Germany. Even if he does, he will have a null effect on what the Allies do; as noted above, they have plenty of good heavy bomber designs and simply don't need a, frankly, piece of crap ballistic missile like the V2. The effects on Germany will be larger since they won't be wasting money and resources on said piece of crap, which might very well find their way into things like Wasserfall, the R4M, jet fighters, and who knows what else.
The only thing he might have an effect on is post-war. If nothing else, von Braun was quite the salesman, and with an extra decade to get used to the US and no annoying Nazi connection (or at least nothing that can't be totally ignored, rather more so than IOTL), he might be able to persuade people to start looking into ballistic missiles a little sooner. With nuclear warheads, even the crap missiles they could produce at the time look relatively good, and they do have advantages over heavy bombers then. Still, it wouldn't be a big effect. Maybe a few years. And it might be counteracted by the lack of disassembled and tested V2s to poke over--now they have to develop all that stuff for the first time, rather than just copying and reverse-engineering. That would slow down both the US and Soviet programs (and the Brits, but they were a third wheel anyways).