Sachverhalt:
A. Der Stadtrat Lenzburg legte vom 16. September bis zum 5. Oktober 2005 ein Baugesuch der Y._, Lenzburg, für den Abbruch der Gebäude Nr. 575 und 576 sowie den Neubau eines Wohn- und Geschäftshauses auf Parz. Nr. 284 (Ziegelackerweg 13) und eines Mehrfamilienhauses auf den Parz. Nr. 284, 3339, 289 bzw. 1898, 2395 und 3352 (Ziegelackerweg 16) in der Ringzone R der Stadt Lenzburg öffentlich auf. Die Ringzone ist mit einer Umgebungsschutzzone überlagert. Zudem besteht für das fragliche Gebiet ein sog. Strukturplan (Strukturplan Altstadt und Umgebung), der das anzustrebende städtebauliche Grundmuster aufzeigt.
Gegen das Bauvorhaben erhoben unter anderem A.X._ und B.X._ als Eigentümer der Parz. Nr. 566 Einsprache.
B. Gegen die am 12. April 2006 unter Bedingungen und Auflagen erteilte Baubewilligung erhoben A.X._ und B.X._ Verwaltungsbeschwerde beim Regierungsrat des Kantons Aargau, der die Beschwerde bezüglich der Liegenschaft Ziegelackerweg 13 teilweise guthiess und die Sache an den Stadtrat Lenzburg zum Neuentscheid zurückwies.
Gegen den Entscheid des Regierungsrates erhoben A.X._ und B.X._ Verwaltungsgerichtsbeschwerde beim Verwaltungsgericht des Kantons Aargau.
C. Am 31. Oktober 2007 erteilte der Stadtrat Lenzburg die Baubewilligung für das geänderte Projekt betreffend das Gebäude Ziegelackerweg 13. Diese Bewilligung blieb unangefochten.
D. Mit Urteil vom 18. Februar 2008 wies das Verwaltungsgericht des Kantons Aargau die bei ihm erhobene Beschwerde ab, soweit es darauf eintrat.
E. Gegen das Urteil des Verwaltungsgerichts erheben A.X._ und B.X._ mit Eingabe vom 14. April 2008 beim Bundesgericht Beschwerde in öffentlich-rechtlichen Angelegenheiten. Sie stellen die folgenden Anträge:
"1 a) Das Urteil des Verwaltungsgerichts des Kantons Aargau vom
18. Februar 2008 sei aufzuheben.
Die Baubewilligung des Stadtrates Lenzburg vom 12. April 2006 sei
aufzuheben.
b) Die Kosten des Verfahrens vor den Vorinstanzen seien der
Beschwerdegegnerin aufzuerlegen.
c) Den Beschwerdeführenden sei für das Verfahren vor den Vorinstanzen
eine Parteientschädigung zuzusprechen.
2 Eventuell sei die Angelegenheit zur Neuentscheidung an das
Verwaltungsgericht des Kantons Aargau zurückzuweisen.
3 Unter gesetzlichen Kosten- und Entschädigungsfolgen."
F. Die Beschwerdegegnerin beantragt in ihrer Stellungnahme, die Beschwerde abzuweisen, soweit darauf einzutreten sei. Das Verwaltungsgericht des Kantons Aargau schliesst in seiner Vernehmlassung auf Abweisung der Beschwerde.

Erwägungen:
1. Das Bundesgericht prüft die Zulässigkeit der Beschwerden von Amtes wegen (<ref-law>; <ref-ruling> E. 1.1 S. 251).
1.1 Das angefochtene Urteil des Verwaltungsgerichts ist ein Entscheid einer letzten kantonalen Instanz (<ref-law>). Ihm liegt ein Beschwerdeverfahren über eine baurechtliche Bewilligung und damit eine öffentlich-rechtliche Angelegenheit zu Grunde. Das Bundesgerichtsgesetz enthält auf dem Gebiet des Raumplanungs- und Baurechts keinen Ausschlussgrund von der Beschwerde in öffentlich-rechtlichen Angelegenheiten (Art. 82 lit. a und Art. 83 BGG). Die Beschwerde in öffentlich-rechtlichen Angelegenheiten nach <ref-law> steht somit grundsätzlich zur Verfügung (vgl. <ref-ruling> E. 1.2 S. 251; 409 E. 1.1 S. 411).
1.1 Das angefochtene Urteil des Verwaltungsgerichts ist ein Entscheid einer letzten kantonalen Instanz (<ref-law>). Ihm liegt ein Beschwerdeverfahren über eine baurechtliche Bewilligung und damit eine öffentlich-rechtliche Angelegenheit zu Grunde. Das Bundesgerichtsgesetz enthält auf dem Gebiet des Raumplanungs- und Baurechts keinen Ausschlussgrund von der Beschwerde in öffentlich-rechtlichen Angelegenheiten (Art. 82 lit. a und Art. 83 BGG). Die Beschwerde in öffentlich-rechtlichen Angelegenheiten nach <ref-law> steht somit grundsätzlich zur Verfügung (vgl. <ref-ruling> E. 1.2 S. 251; 409 E. 1.1 S. 411).
1.2 1.2.1 Zur Beschwerde in öffentlich-rechtlichen Angelegenheiten ist nach <ref-law> berechtigt, wer vor der Vorinstanz am Verfahren teilgenommen oder keine Möglichkeit zur Teilnahme erhalten hat (lit. a), durch den angefochtenen Entscheid besonders berührt ist (lit. b) und ein schutzwürdiges Interesse an dessen Aufhebung oder Änderung besitzt (lit. c). Verlangt ist somit neben der formellen Beschwer, dass der Beschwerdeführer über eine spezifische Beziehungsnähe zur Streitsache verfügt und einen praktischen Nutzen aus der Aufhebung oder Änderung des angefochtenen Entscheids zieht. Die Nähe der Beziehung zum Streitgegenstand muss bei Bauprojekten insbesondere in räumlicher Hinsicht gegeben sein. Ein schutzwürdiges Interesse liegt vor, wenn die tatsächliche oder rechtliche Situation des Beschwerdeführers durch den Ausgang des Verfahrens beeinflusst werden kann (<ref-ruling> E. 1.3 S. 413, 400 E. 2.2 S. 404 f., je mit Hinweisen).
1.2.2 Die Beschwerdeführer haben am vorinstanzlichen Verfahren teilgenommen. Ihre Liegenschaft und das rund 20 m entfernte Baugrundstück stehen in Sichtverbindung. Vom fraglichen Bauvorhaben und dessen vorhersehbaren Auswirkungen sind sie in eigenen schutzwürdigen Interessen faktisch betroffen (Lärmimmissionen, erhöhte Einsehbarkeit des Grundstücks der Beschwerdeführer, Lichtentzug durch den Baukörper) und zwar in einem erheblich höheren Mass, als es für die Allgemeinheit zutrifft. Dass der Verzicht auf das Bauvorhaben für die Beschwerdeführer einen praktischen Nutzen zur Folge hätte, ist offensichtlich. Sie sind somit gestützt auf <ref-law> zur Beschwerde befugt.
1.3 Der angefochtene Entscheid stützt sich in der Sache auf kantonales bzw. kommunales Planungs- und Baurecht. Da dessen Verletzung keinen Beschwerdegrund nach <ref-law> darstellt, kann der Entscheid nur darauf überprüft werden, ob er auf willkürlicher Gesetzesanwendung beruht oder sonst wie gegen übergeordnetes Recht verstösst (vgl. <ref-ruling> E. 1.2.1 S. 251 f.).
Die Beschwerdeführer machen geltend, der angefochtene Entscheid verletze das Willkürverbot (<ref-law>) sowie ihren Anspruch auf rechtliches Gehör (<ref-law>, § 22 Abs. 1 KV/AG). Sie bringen somit zulässige Beschwerdegründe vor.
1.4 Da auch die übrigen Sachurteilsvoraussetzungen erfüllt sind, ist auf die Beschwerde vorbehältlich genügend begründeter Rügen (Art. 106 Abs. 2 i.V.m. <ref-law>) einzutreten.
2. Die Beschwerdeführer rügen in verschiedenen Zusammenhängen, die Vorinstanz sei nicht ernsthaft auf ihre Argumente eingegangen und habe in ihrer Entscheidbegründung wesentliche Vorbringen ausser Acht gelassen.
2.1 Aus dem Anspruch auf rechtliches Gehör leitet das Bundesgericht in ständiger Rechtsprechung die Pflicht der Behörden ab, ihre Verfügungen und Entscheide zu begründen (<ref-ruling> E. 2b S. 102; zu Art. 4 aBV grundlegend BGE 112 la 107 E. 2b S. 109 f.; vgl. auch Botschaft des Bundesrates über eine neue Bundesverfassung vom 20. November 1996, BBl 1997 I 182 zu Art. 25). Der Grundsatz des rechtlichen Gehörs als persönlichkeitsbezogenes Mitwirkungsrecht verlangt, dass die Behörde die Vorbringen des vom Entscheid in seiner Rechtsstellung Betroffenen auch tatsächlich hört, sorgfältig und ernsthaft prüft und in der Entscheidfindung berücksichtigt. In diesem Sinne müssen wenigstens kurz die Überlegungen genannt werden, von denen sich die Behörde leiten liess und auf welche sich ihr Entscheid stützt (<ref-ruling> E. 3.2 S. 236, 126 I 97 E. 2b S. 102, je mit Hinweisen). Was in diesem Sinne entscheiderheblich ist, ergibt sich aus der Begründung des angefochtenen Entscheids oder aus einer davon abweichenden Auffassung der Rechtsmittelinstanz (<ref-ruling> E. 3b S. 334). Nicht erforderlich ist jedoch, dass sich die entscheidende Instanz mit sämtlichen Parteivorbringen, zumal wenn diese unerheblich oder unzureichend substanziiert sind, auseinandersetzt.
2.2 Die Rüge, die Vorinstanz sei über wesentliche Beschwerdevorbringen zu Tragweite und Bindungswirkung des Strukturplans hinweggegangen (insbesondere Beschwerde, Ziff. II.2c, S. 7 ff.), ist unbegründet. Die Vorinstanz hat sich, insbesondere in E. 2.2 ff., mit den entsprechenden Vorbringen, soweit es diese als wesentlich erachtete, durchaus befasst; ihrem Urteil sind die massgeblichen Erwägungen hinreichend deutlich zu entnehmen. In Wirklichkeit bezieht sich die in der Beschwerde diesbezüglich erhobene Kritik auf die Erwägungen der Vorinstanz zur Sache selbst und ist in jenem Zusammenhang zu behandeln (vgl. E. 3 nachfolgend). Gleiches gilt, soweit die Beschwerdeführer diese Rüge auch im Zusammenhang mit dem in der Baubewilligung gewährten Grenzabstand zur Parzelle Nr. 1912 von einem Meter erheben. Die Vorinstanz hat sich mit den Vorbringen der Beschwerdeführer zu diesem Thema in E. 3 sinngemäss auseinandergesetzt. Aufgrund verständlich dargelegter und nachvollziehbarer Erwägungen ist sie jedoch zum Ergebnis gelangt, dass in der Ringzone die schematische Anwendung eines bestimmten Grenzabstandes untypisch und rechtsungleich wäre. Damit ist dem Anspruch auf rechtliches Gehör Genüge getan. Auf die materielle Tragweite dieser Rügen wird in E. 4 nachfolgend nachgegangen.
2.3 Ferner rügen die Beschwerdeführer als Gehörsverweigerung, dass das Verwaltungsgericht nicht auf ihr Vorbringen eingegangen sei, der Eigentümer der Parzelle Nr. 1912 müsse die Freiheit haben, sein Grundstück mit einer 1,8 m hohen Mauer zu umgeben (gemäss § 19 Abs. 1 lit. a der aargauischen Allgemeinen Verordnung zum Baugesetz [ABauV/AG]), in einem Grenzabstand von 2 m eine 3 m hohe Kleinbaute zu erstellen (gemäss § 18 ABauV/AG) oder Obstbäume in einer Entfernung von 3 m zur Grenze anzupflanzen (gemäss § 88 Abs. 2 des aargauischen Einführungsgesetzes zum Schweizerischen Zivilgesetzbuch und Partnerschaftsgesetz vom 27. März 1911 [EG ZGB/AG]). Die Erstellung solcher Bauten bzw. die Anpflanzung von Obstbäumen auf dem zwischen der Parzelle der Beschwerdeführer und dem Baugrundstück gelegenen Teil der Parzelle Nr. 1912 steht in keiner Weise zur Diskussion. Die Vorinstanz hat daher keine Gehörsverletzung begangen, als sie auf die diesbezüglichen Vorbringen der Beschwerdeführer nicht ausdrücklich eingegangen ist.
2.4 Unbehelflich ist der appellatorische Hinweis, dass die Vorinstanz entgegen ihrer Praxis keinen Augenschein durchgeführt habe, zumal die Beschwerdeführer einen solchen Antrag vor der Vorinstanz nicht gestellt haben.
3. Die Beschwerdeführer werfen dem Verwaltungsgericht vor, die Verbindlichkeit des Strukturplans und den Umstand verkannt zu haben, dass der Stadtrat seine Kompetenz, bei Vorliegen anders gearteter Lösungen von der im Strukturplan vorgesehenen Grundstruktur des Wechsels von Bau- und Freiflächen abzuweichen, überschritten habe. Indem das Verwaltungsgericht zulasse, dass das Vorhaben von diesem Grundmuster abweiche und eine im Strukturplan vorgesehene Freifläche überbaut werde, verfalle es in Willkür.
3.1 Nach bundesgerichtlicher Praxis liegt Willkür vor, wenn der angefochtene Entscheid offensichtlich unhaltbar ist, mit der tatsächlichen Situation in klarem Widerspruch steht, eine Norm oder einen unumstrittenen Rechtsgrundsatz krass verletzt oder in stossender Weise dem Gerechtigkeitsgedanken zuwiderläuft. Das Bundesgericht hebt einen Entscheid jedoch nur auf, wenn nicht bloss die Begründung, sondern auch das Ergebnis unhaltbar ist; dass eine andere Lösung ebenfalls als vertretbar oder gar zutreffender erscheint, genügt nicht (<ref-ruling> E. 5.4 S. 149, 134 II 124 E. 4.1 S. 133, je mit Hinweisen).
3.2 Im Abschnitt "Planungsinstrumente" bestimmt § 7 der Bauordnung der Stadt Lenzburg vom 22. Mai 1997 (BO) unter dem Randtitel "Strukturpläne" folgendes:
"1 Für die im Bauzonenplan mit schwarzen Punkten umrahmten zwei Gebiete "Altstadt und Umgebung" und "Bahnhof - Bahnhofstrasse - Malagarain" bestehen Strukturpläne im Massstab 1:1000. Es können weitere Strukturpläne erlassen werden.
2 Die Strukturpläne zeigen das anzustrebende städtebauliche Grundmuster auf, insbesondere die erhaltenswerten Bauten, die Standorte für Neubauten und die Freiräume.
3 Von der im Plan vorgesehenen Struktur kann abgewichen werden, sofern eine städtebaulich gleichwertige Lösung aufgezeigt wird. Der Gemeinderat entscheidet in der Regel aufgrund von Anträgen der zuständigen Kommissionen."
Zudem nimmt die Bauordnung auch im Zusammenhang mit einzelnen Zonenvorschriften auf die Strukturpläne Bezug. So lautet der die hier massgebliche Ringzone betreffende § 20 Abs. 2 BO (Randtitel "Bauweise") wie folgt:
"2 Bauliche Erneuerungen und die Schliessung von Baulücken haben sich gut in das bestehende, historische Ortsbild einzuordnen und dürfen insbesondere den Charakter der Altstadt und der weiteren Schutzzonen nicht beeinträchtigen. Die gewünschte Struktur ist im Strukturplan "Altstadt und Umgebung" festgehalten."
3.3 Die Beschwerdeführer machen geltend, dass dem Strukturplan eine gegenüber sonstigen Richtplänen erhöhte Verbindlichkeit zukomme. Sie begründen dies damit, dass die vom Einwohnerrat festgesetzte Bauordnung verschiedentlich auf den vom Stadtrat (damals: Gemeinderat) beschlossenen Strukturplan verweise und diesen somit gleichsam zu deren Teilinhalt mache, sowie auch damit, dass die Bauordnung etwas später (22. Mai 1997) erlassen wurde als der am 30. April 1997 beschlossene Strukturplan.
Strukturpläne haben unbestrittenermassen Richtplancharakter, sind also behörden-, aber nicht grundeigentümerverbindlich; insbesondere sind sie keine Sondernutzungspläne. § 7 Abs. 3 BO gibt dem Stadtrat die Kompetenz, bei "städtebaulich gleichwertigen" Lösungen vom Strukturplan abzuweichen. Es ist daher nicht willkürlich, wenn das Verwaltungsgericht das Kriterium der städtebaulichen Gleichwertigkeit als massgeblich für die Zulässigkeit von Abweichungen gegenüber den im Strukturplan enthaltenen Festlegungen erachtet und demzufolge die als "Richtplaninhalt" ausgewiesenen Bauoptionen und Freiflächen lediglich als nicht zwingende Möglichkeiten ansieht, von denen abgewichen werden kann, solange gewährleistet bleibt, dass der vom Strukturplan angestrebte Wechsel zwischen Bauten und Freiräumen als städtebauliches Grundmuster erhalten bleibt.
Das Verwaltungsgericht hält unwidersprochen fest, dass das vorliegende Projekt aus einem Architekturwettbewerb hervorgegangen ist und unter Mitwirkung der Stadtbildkommission und des kantonalen Ortsbildpflegers entwickelt wurde, nach dem Urteil dieser Stellen urbanistische Qualität aufweist und sich gut in das vorhandene städtebauliche Muster einfügt. Es ist daher nicht willkürlich, wenn das Verwaltungsgericht sich der Beurteilung seiner Vorinstanzen anschliesst, welche die städtebauliche Gleichwertigkeit mit den Vorgaben des Strukturplans bejaht haben. Die einschränkende Auffassung der Beschwerdeführer, den expliziten Festlegungen des Strukturplans komme, zumal angesichts der bereits in erheblichem Ausmass vorhandenen Bauten, eine weitergehende Verbindlichkeit zu, so dass von einzelnen im Plan festgehaltenen "Bauoptionen" und "Freiräumen" höchstens in untergeordnetem Ausmass abgewichen werden könne, ist zumindest nicht zwingend. Sie findet weder in der Bauordnung noch im Wortlaut der Richtplanfestlegungen eine Stütze und lässt die Auffassung des Verwaltungsgerichts, welches unter Beachtung der Planungsautonomie der Stadt Lenzburg im fraglichen Bauvorhaben und den ihm zugrunde liegenden, nachvollziehbaren Erwägungen keinen Verstoss gegen die Bauordnung der Stadt Lenzburg erblickt, nicht als willkürlich erscheinen.
3.4 Die Beschwerdeführer werfen dem Verwaltungsgericht und den kantonalen Vorinstanzen einen Verstoss gegen Treu und Glauben vor, indem sie die Erwartung der "Bewohner und Eigentümer der andern angrenzenden Liegenschaften", die auf das Fortbestehen der bestehenden Freifläche hätten vertrauen dürfen, enttäuscht hätten.
Da der Strukturplan nach § 6 Abs. 1 BO nicht grundeigentümerverbindlich ist und § 7 Abs. 3 BO zudem ein Abweichen von der im Plan aufgezeigten Struktur zulässt, sofern eine städtebaulich gleichwertige Lösung aufgezeigt wird, stellt er gegenüber den Grundeigentümern keine behördliche Zusicherung bestimmter konkreter Zustände (Fortbestehen der bestehenden Freifläche) oder Nutzungsmöglichkeiten dar. Die Vorinstanz hat daher mit ihrem Entscheid, mit welchem sie die angefochtene Baubewilligung des Stadtrates Lenzburg betreffend Liegenschaft Ziegelackerweg 16 geschützt hat, keine aus der Bundesverfassung ableitbaren Ansprüche der Beschwerdeführer auf Behandlung nach Treu und Glauben verletzt.
4. Die Beschwerdeführer erblicken Willkür und Rechtsungleichheit im Umstand, dass das Verwaltungsgericht den im Bauprojekt vorgesehenen Grenzabstand des südlichen Teils des projektierten Gebäudes von der Westgrenze der Parzelle Nr. 1912 unbeanstandet gelassen hat. Das Grundstück der Beschwerdeführer grenzt zwar nicht unmittelbar an das Baugrundstück an, liegt aber doch in erheblicher Nähe (vgl. oben E. 1.2.2), und die Frage des Grenzabstandes wirkt sich im Ergebnis auch auf den Abstand der projektierten Baute zum Grundstück und zum Gebäude der Beschwerdeführer aus.
4.1 Die Gemeinden haben nach § 47 Abs. 1 des aargauischen Gesetzes über Raumplanung, Umweltschutz und Bauwesen vom 19. Januar 1993 (Baugesetz, BauG/AG) Grenz- und Gebäudeabstände vorzuschreiben. Die Bauordnung der Stadt Lenzburg enthält in § 10 entsprechende Vorschriften; für verschiedene Zonen (Altstadtzone [§ 11 ff.], übrige sog. Schutzzonen [§ 18 f.], Ringzone [§ 20] und Spezialzone [§ 21 BO]) werden die Grenzabstände laut § 10 BO aber nicht generell-abstrakt, sondern im Einzelfall durch den Gemeinderat (heute: Stadtrat) festgelegt, was § 20 Abs. 3 BO für die Ringzone eigens wiederholt. Die Beschwerdeführer rügen diese Regelung nicht als gesetzwidrig.
4.2 Der Stadtrat hat erwogen, dass die analoge Anwendung der Grenzabstandsregelung einzelner anderer Zonen - so insbesondere der von den Beschwerdeführern postulierte Grenzabstand von 4 Metern der Zone WG 11.5 - angesichts der besonderen urbanistischen Aufgabenstellung in der Ringzone nicht zu befriedigenden Lösungen führe. Die vorliegende Lösung habe er angesichts des hier vorherrschenden unregelmässigen Überbauungsmusters und der bei bestehenden Gebäuden gegebenen geringen oder sogar fehlenden Grenzabstände getroffen.
4.2.1 Die Beschwerdeführer erachten einen Grenzabstand von weniger als 4 Metern als ungerechtfertigt. Sie legen dar, dass diejenigen bestehenden Bauten, welche einen geringeren oder keinen Grenzabstand aufwiesen, entweder lange vor dem Erlass der Bauordnung von 1997 erstellt worden seien oder sich sonst an die Bauoptionen des Strukturplans hielten. Nach ihrer Auffassung verfällt das Verwaltungsgericht in Willkür und Rechtsungleichheit, wenn es geringere Grenzabstände auch bei Bauvorhaben ausserhalb der im Strukturplan enthaltenen Bauoptionen zulässt.
4.2.2 Wie in E. 3 hiervor dargelegt wurde, durfte das Verwaltungsgericht ohne Willkür erwägen, dass die Bauoptionen des Strukturplans nicht zwingende Vorgaben sind und auch abweichende bzw. andere Lösungen zulassen, die mit vertretbaren Gründen als städtebaulich gleichwertig angesehen werden können. Diese Erwägungen gelten auch im vorliegenden Zusammenhang. Insoweit ist den Rügen der Willkür und der Rechtsungleichheit, soweit sie überhaupt als hinreichend belegt anzusehen sind, der Boden entzogen. - Eine städtebaulich gleichwertige Abweichung von den Baubereichen des Strukturplans bildet auch nicht per se eine Verletzung der Rechtsgleichheit. Vielmehr ist nach diesem Grundrecht Gleiches nach Massgabe seiner Gleichheit gleich, Ungleiches aber ungleich zu behandeln. Wie das Verwaltungsgericht darlegt, hat der kommunale Gesetzgeber die Grenzabstandsregelung für die Ringzone und andere besondere Zonen gerade im Hinblick auf die besonderen Verhältnisse des Einzelfalls getroffen, damit der Stadtrat hier jeweils die von der Rechtsgleichheit gebotenen Differenzierungen vornehmen kann. Die Beschwerdeführer bringen gegen diese Argumentation nichts Durchschlagendes vor. Wenn das Verwaltungsgericht bei dieser Sachlage die Erwägungen des Stadtrates sachlich und auch mit Rücksicht auf die Gemeindeautonomie unbeanstandet gelassen hat, liegt darin kein Verstoss gegen die Rechtsgleichheit.
4.3 Dass Grenz- und Gebäudeabstände unterschiedliche Funktionen haben können, geht aus dem angefochtenen Entscheid selber hervor. Die Beschwerdeführer rügen nicht, dass bestimmte Vorschriften über Gebäudeabstände verletzt seien. Sie deuten indes an, es würde zu Rechtsungleichheiten führen, wenn der früher Bauwillige seine Bauten bis an die Grenze setzen könnte, während der später bauwillige Nachbar seine Bauten dann über den vorgeschriebenen Grenzabstand hinaus zurücksetzen müsste, um den Gebäudeabstand einzuhalten.
Die sehr kleine Parzelle Nr. 566 der Beschwerdeführer ist praktisch vollständig überbaut; nach Westen hin ist lediglich ein sehr schmaler Landstreifen noch frei. Die Beschwerdeführer machen nicht geltend, dass eine Überbauung dieses Streifens wegen des Gebäudeabstandes zur projektierten Baute verunmöglicht werde. Unter dem Gesichtspunkt der Rechtsgleichheit erscheint es daher nicht als verfassungswidrig, wenn für den südlichen Teil des strittigen Bauvorhabens gegenüber der Westgrenze der Parzelle Nr. 1912 ein Grenzabstand von lediglich einem Meter vorgesehen ist.
5. Die Beschwerdeführer rügen als willkürlich, dass die Vorinstanz zwar zu Recht festhalte, der Regierungsrat des Kantons Aargau hätte nach dem Grundsatz der Einheit der Baubewilligung die bei ihm angefochtene Baubewilligung richtigerweise als Ganzes aufheben müssen, dann aber ohne Begründung ausführe, dass dieses gebotene Vorgehen keine Auswirkungen auf den Kostenentscheid gehabt hätte. Richtigerweise hätten bei diesem Sachausgang der Bauherrschaft die Kosten und eine Parteientschädigung auferlegt werden müssen (§ 33 Abs. 2 und § 36 des aargauischen Gesetzes über die Verwaltungsrechtspflege vom 9. Juli 1968 [Verwaltungsrechtspflegegesetz, VRPG/AG]). Der Entscheid des Verwaltungsgerichts sei insoweit willkürlich und verstosse mangels hinreichender Begründung auch gegen den Anspruch der Beschwerdeführer auf rechtliches Gehör.
5.1 Die Regelung des Verfahrens in kantonalen Verwaltungssachen ist Sache des kantonalen Rechts. Das Bundesgericht kann dessen Anwendung nur im Rahmen der Beschwerdegründe nach Art. 95 f. BGG überprüfen; im vorliegenden Zusammenhang wird in der Sache denn auch nur der Beschwerdegrund des Verstosses gegen das Willkürverbot angerufen.
5.2 Nach Auffassung des Verwaltungsgerichts hätte der Regierungsrat in seinem Entscheiddispositiv die Beschwerde teilweise gutheissen, aber den angefochtenen Entscheid (in vollem Umfang) aufheben müssen. Es leuchtet ein, dass - soweit der Grundsatz der Einheit der Baubewilligung gilt - die Gutheissung eines Rechtsmittels zur Aufhebung der Bewilligung insgesamt führen muss; dies auch dann, wenn die Gutheissung nur in einem Teilaspekt erfolgt ist. Hievon zu unterscheiden ist die Frage nach den Kosten- und Entschädigungsfolgen eines solchen Entscheides. Es handelt sich um eine Folgefrage, bei der Differenzierungen nicht zum Vornherein ausgeschlossen sind.
Nach § 33 Abs. 2 VRPG/AG sind in Beschwerdeverfahren die Kosten in der Regel dem Unterliegenden aufzuerlegen (Satz 1). Bei teilweiser Gutheissung der Beschwerde sind die Kosten anteilmässig zu verlegen (Satz 2). Die Beschwerdeführer treten der Auffassung der Vorinstanz, dass nach aargauischem Recht eine teilweise Gutheissung der Beschwerde, wenn auch mit vollständiger Aufhebung der angefochtenen Baubewilligung, angebracht war, nicht entgegen. Ist demnach eine Teilgutheissung eines Rechtsmittels in Verbindung mit vollständiger Aufhebung des angefochtenen Entscheids möglich, so steht die darauf aufbauende Erwägung der Vorinstanz, dass ein solcher Entscheid an der vom Regierungsrat getroffenen Kostenregelung nichts geändert hätte, zumindest nicht in offenkundigem Widerspruch zur einschlägigen Verfahrensordnung. Da die Beschwerdeführer diesbezüglich keine weiteren Argumente gegen die Auffassung der Vorinstanz vorbringen, dringen ihre Rügen nicht durch. - Im Zusammenhang mit der Parteientschädigung gilt sinngemäss dasselbe. Zwar verweist § 36 Abs. 1 VRPG/AG nicht explizit auf § 33 Abs. 2 VRPG/AG, geht aber von vergleichbaren Grundsätzen aus, indem der obsiegenden Partei eine angemessene Entschädigung zuzusprechen (Satz 1) und diese den Umständen entsprechend dem Unterliegenden oder dem interessierten Gemeinwesen oder beiden anteilweise aufzuerlegen ist (Satz 2). Es kann daher auf die vorstehenden Erwägungen verwiesen werden.
5.3 Unbegründet ist die auch in diesem Zusammenhang erhobene Rüge mangelnder Begründung des angefochtenen Entscheides. Es kann diesbezüglich auf die allgemeinen Überlegungen in E. 2 hiervor verwiesen werden. Die Erwägungen im angefochtenen Urteil sind diesbezüglich zwar knapp, lassen aber die leitenden Gedanken des Verwaltungsgerichts durchaus erkennen, so dass auch eine sachgerechte Anfechtung möglich war.
6. Die Beschwerde ist daher abzuweisen, soweit darauf einzutreten ist.
Dem Ausgang des vorliegenden Verfahrens entsprechend sind die Gerichtskosten den unterliegenden Beschwerdeführern aufzuerlegen (<ref-law>). Diese haben die private Beschwerdegegnerin für das bundesgerichtliche Verfahren angemessen zu entschädigen (Art. 68 Abs. 1, 2 und 4 BGG).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen, soweit darauf eingetreten wird.
2. Die Gerichtskosten von Fr. 3'000.-- werden den Beschwerdeführern auferlegt.
3. Die Beschwerdeführer haben der privaten Beschwerdegegnerin für das bundesgerichtliche Verfahren unter solidarischer Haftung eine Parteientschädigung von insgesamt Fr. 3'000.-- zu bezahlen.
4. Dieses Urteil wird den Parteien, dem Stadtrat Lenzburg, dem Departement Bau, Verkehr und Umwelt und dem Verwaltungsgericht des Kantons Aargau, 3. Kammer, schriftlich mitgeteilt.
Lausanne, 24. Oktober 2008
Im Namen der I. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Der Gerichtsschreiber:
Féraud Kappeler