NYC und MIA sind absolute Rennstrecken, da kannst Du mit fast jeder Airline fliegen, die Preise sind meist ziemlich gut. Geh einfach in eines der großen Flugportale wie ebookers, opodo, expedia usw. und schaue, was die zu bieten haben.
Ab Düsseldorf bietet sich auf der Route Air Berlin an, da die diese Ziele direkt bedienen, ist allerdings eine relativ einfache Airline. BA, KLM/Air France und LH sind mögliche Alternativen mit Umsteigen an den jeweiligen Hubs.
Ihr habt grundsätzlich die Möglichkeit, den inneramerikanischen Flug auf dem gleichen Ticket wie die Transatlantikflüge zu buchen, also als weitere Flugstrecke eingeben. Ob man das macht oder separat bucht, ist ein Rechenexemple. Wenn Ihr die inneramerikanische Strecke separat bucht, müsst Ihr berücksichtigen, dass da noch zusätzliche Gebühren für das Gepäck berechnet werden, meist ca. 25$ pro Gepäckstück. Für die Strecke Washington - Orlando kann ich Jet Blue wärmstens empfehlen.
Palm Beach finde ich persönlich hässlich, ich würde immer die Golfküste (Naples, Ft. Myers) vorziehen. Ihr könntet z.B. von Orlando aus in ca. 3,5h nach Ft. Myers/Naples fahren. Von dort geht es weiter nach Homestead/Florida City, mit einem kurzen Abstecher in den Everglades NP (Anhinga Trail). Bis Key West sind es dann nochmals rund 2h. Vor dem Heimflug bleibt Ihr dann ein paar Tage im Großraum Miami.