Sachverhalt: A. Am 4. April 2006 genehmigte der Regierungsrat des Kantons Solothurn den Teilzonen- und Gestaltungsplan "Fegetzhof" mit Sonderbauvorschriften. Am 25. August 2008 reichten die Eheleute Y._ ein Gesuch für den Bau eines Einfamilienhauses auf der im Eigentum des Kantons Solothurn stehenden und im Planperimeter liegenden Parzelle Nr. 6780 ein. Gegen das Baugesuch erhoben die Eheleute X._ sowie die Eheleute Z._ Einsprache. Mit Beschluss vom 25. November 2008 wies die Baukommission der Stadt Solothurn die Einsprachen ab und erteilte die Baubewilligung. Dagegen erhoben die Eheleute X._ beim Verwaltungsgericht des Kantons Solothurn Beschwerde. Gleichzeitig fochten sie einen zweiten Entscheid der Baukommission an, mit welchem diese das Baugesuch eines weiteren Gesuchstellers für die benachbarte Parzelle Nr. 6564 gutgeheissen hatte. Mit Urteil vom 16. Juni 2009 hiess das Verwaltungsgericht diese zweite Beschwerde gut und wies die Angelegenheit zu neuem Entscheid an die Baukommission zurück. Die Beschwerde gegen das Baugesuch der Eheleute Y._ wies es dagegen ab. B. Mit Beschwerde in öffentlich-rechtlichen Angelegenheiten an das Bundesgericht vom 25. August 2009 beantragen die Eheleute X._, das Urteil des Verwaltungsgerichts vom 16. Juni 2009 sei, insoweit es das Baugesuch der Eheleute Y._ betreffe, aufzuheben und die Sache sei zur neuen Entscheidung an das Verwaltungsgericht, eventualiter an die Baukommission zurückzuweisen. In verfahrensrechtlicher Hinsicht beantragen sie, es sei im Verfahren vor Bundesgericht ein Augenschein durchzuführen und der Beschwerde sei die aufschiebende Wirkung zuzuerkennen. Das Verwaltungsgericht, die Baukommission, der Kanton Solothurn sowie die Eheleute Y._ beantragen in ihrer jeweiligen Vernehmlassung die Abweisung der Beschwerde, soweit darauf einzutreten sei. In ihrer Stellungnahme dazu halten die Beschwerdeführer im Wesentlichen an ihren Anträgen und Rechtsauffassungen fest. Mit Präsidialverfügung vom 18. September 2009 hat das Bundesgericht der Beschwerde die aufschiebende Wirkung zuerkannt.