Sachverhalt: A. Die Stadt Zürich will auf ihrem Gemeindegebiet einen durchgehenden Seeuferweg entlang des Zürichseeufers realisieren. Bei der Bucht zwischen der Roten Fabrik (einem Zentrum für alternative Kultur in einem historischen Fabrikgebäude) und dem Hafen Wollishofen ist ein Steg geplant. Das Projekt umfasst eine 284 m lange und 2,8 m breite, im Abstand von 15 m auf Pfählen fundierte Stahlkonstruktion mit bogenförmigem, mehrfach geknicktem Verlauf in bis zu 100 m Entfernung vom Ufer. Der Steg ist mit einem rund 1 m hohen Geländer versehen; die lichte Höhe der Gehfläche liegt rund 1,5 m über dem Mittelwasserstand von 406 m.ü.M. Am höchsten Punkt steigt die lichte Höhe auf 408 m.ü.M. an, um die Durchfahrt kleiner Boote zu ermöglichen. Die Plätze am Ufer bei den Steganschlüssen sollen neu gestaltet werden. Als ökologische Ersatzmassnahmen sollen eine bestehende Ufertreppe abgebrochen, ein Flachufer mittels Kiesschüttung gestaltet und ein Brutfloss für Flussseeschwalben erstellt werden. Am 17. Juni 2009 setzte der Zürcher Stadtrat das Projekt gemäss Auflageplan fest und wies mehrere gegen das Stegbauprojekt eingegangene Einsprachen ab. Gleichzeitig eröffnete er die Verfügung der kantonalen Baudirektion vom 6. April 2009 (mit einer am 22. April 2009 wiedererwägungsweise beschlossenen Dispositivänderung), mit der eine wasserrechtliche Konzession, eine fischereigesetzliche Bewilligung, eine raumplanungsrechtliche Ausnahmebewilligung für Bauten ausserhalb von Bauzonen, eine Bewilligung aufgrund der Landanlagekonzession sowie eine wasserbaupolizeiliche Ausnahmebewilligung erteilt wurden. B. Dagegen erhoben drei Eigentümer von Grundstücken in der Nähe des projektierten Stegs (X._, Y._ und Z._; im Folgenden: die Eigentümer bzw. die Beschwerdeführer) am 31. Juli 2009 Rekurs an den Regierungsrat des Kantons Zürich. Dieser wies den Rekurs am 23. Juni 2010 ab, soweit er darauf eintrat. Am 13. Januar 2010 hiess das Verwaltungsgericht die dagegen erhobene Beschwerde der Eigentümer teilweise gut und wies die Sache zu neuem Entscheid in rechtskonformer Zusammensetzung des Spruchkörpers an den Regierungsrat zurück. Mit Beschluss vom 17. August 2011 entschied der Regierungsrat erneut, ohne den im Ausstand befindlichen Baudirektor. Er wies den Rekurs abermals ab, soweit er darauf eintrat. C. Gegen den Rekursentscheid erhoben die Eigentümer am 24. September 2011 wiederum Beschwerde ans Verwaltungsgericht. Sie beantragten in der Hauptsache, auf den geplanten Steg sei zu verzichten; eventualiter verlangten sie diverse Projektänderungen. Am 21. Dezember 2011 wies das Verwaltungsgericht die Beschwerde ab, soweit es darauf eintrat. Die dagegen gerichtete Beschwerde der Eigentümer hiess das Bundesgericht am 7. September 2012 gut (Urteil 1C_86/2012). Es hob den verwaltungsgerichtlichen Entscheid auf und wies die Sache an das Verwaltungsgericht zurück, um zunächst über den Antrag auf Einholung eines neuen Gutachtens der kantonalen Natur- und Heimatschutzkommission (NHK) und anschliessend in der Sache selbst neu zu entscheiden. D. Am 29. November 2012 beauftragte das Verwaltungsgericht die NHK mit der Erstellung eines Gutachtens zur Frage: "Wie ist das Projekt zum Bau eines Stegs, der zwischen der Roten Fabrik und dem Hafen Wollishofen über den Zürichsee führt, unter Gesichtspunkten des Natur- und Heimatschutzes zu beurteilen? Wie würde sich der geplante Seesteg auf das Orts- und Landschaftsbild auswirken?". In ihrem Gutachten vom 11. Februar 2013 beurteilte die NHK das Projekt als schwere Beeinträchtigung des Landschafts- und Ortsbilds. Sie beantragte, es seien einfachere und dem Schutzgebiet des Seebeckens der Stadt Zürich adäquatere Wegvarianten auszuarbeiten. Es sollte eine Lösung gefunden werden, welche die geschützte Bucht im Seebecken landseitig umgehe. Die Stadt Zürich nahm dazu am 27. März 2013 Stellung und beantragte, der Antrag der NHK sei abzuweisen. Am 29. Mai 2013 wies das Verwaltungsgericht die Beschwerde ab, soweit es darauf eintrat. E. Gegen den verwaltungsgerichtlichen Entscheid haben die Eigentümer am 12. Juli 2013 Beschwerde in öffentlich-rechtlichen Angelegenheiten ans Bundesgericht erhoben. Sie beantragen, der angefochtene Entscheid sei aufzuheben, zusammen mit der Festsetzung des Stadtrats Zürich vom 17. Juni 2009 und den Verfügungen der Baudirektion vom 6. bzw. 22. April 2009. Eventualiter verlangen sie: - der Steg sei höchstens 1,5 Meter breit möglichst wassernah mit einem Durchlass für Schiffe und in einem einzigen Bogen ohne jedwede Aufenthaltsflächen zu gestalten und die Passage sei täglich bei Einbruch der Dunkelheit von beiden Seiten zu verschliessen, - die Ausgleichsmassnahme auf dem südlichen Gelände der Henneberg'schen Seidenweberei (Rote Fabrik) sei so auszugestalten, dass der Bucht die überbaute Wasserfläche wieder zugeführt werde, - auf die beidseits des Stegs geplanten Anpassungs- und Neugestaltungsarbeiten sei zu verzichten, insbesondere auf das Fällen sämtlicher grossen Bäume; subeventualiter sei zumindest die bestehende Bepflanzung mit den grossen alten Pappeln zu belassen und in die Gestaltung einzubeziehen, - auf die Umgestaltung der Hafenanlage im angrenzenden Bereich des geplanten Stegs sei zu verzichten, insbesondere auf die Neupflanzung von Säulenpappeln und die Errichtung einer weiteren "Begegnungszone". Für den Fall einer erneuten Rückweisung sei ein gerichtlicher Augenschein durchzuführen, eventualiter (bei Nichtrückweisung) ein bundesgerichtlicher Augenschein anzuordnen. F. Die Stadt Zürich schliesst auf Abweisung der Beschwerde. Das Verwaltungsgericht beantragt die Abweisung der Beschwerde, soweit darauf einzutreten sei. Die kantonale Volkswirtschaftsdirektion verzichtet mit Hinweis auf die Vorakten auf eine Stellungnahme. Das Bundesamt für Umwelt (BAFU) verweist auf seine Stellungnahme vom 21. Mai 2012 im Verfahren 1C_86/2012. Das Bundesamt für Raumentwicklung (ARE) hat auf eine Stellungnahme verzichtet. G. In ihrer Replik halten die Beschwerdeführer an ihren Anträgen fest. 