I don't see any reason why fiscal conservatives would be worried about Rudy, who is - other than possibly Fred - the best candidate in the race on taxes and spending. I'm not thrilled with Huckabee anywhere near the executive branch, but picking him would send the clearest possible signal about Rudy's desire to reach an accomodation with social conservatives.
I agree that a ticket with Rudy, Huckabee, Romney or McCain on it would be mistrusted by the immigration hawks.
The city mouse/country mouse ticket would be the most obvious example of a mismatched ticket since Dukakis/Bentsen and maybe since JFK/LBJ; Rudy and Huck are just so radically different in their styles and their cultural backgrounds. But don't neglect one important point: they would be two Washington outsiders with substantial executive experience running against a ticket headed by a Senator who has been in DC since 1993 and has never run anything on her own, and possibly including another Senator with no executive experience, whether it be Obama or some of the others on Hillary's short list. There's a lot to be said for that.