I've sort of hacked together templates for Tarquin's Paddington and Montparnasse proposed skins as Smarty templates, and stuffed and prodded it into the development branch of MediaWiki.
Go on down to test.wikipedia.org, log in, and pick the new skins. (Warning: very VERY incomplete! Lots of links not showing pretty text yet.)
Smarty templates get compiled down to PHP scripts, so "in theory" it shouldn't be slower than writing the interface in raw php. The advantage is in maintainability; I've attached the 4k Paddington template file for comparison against the current combined 96k of OutputPage and Skin which contain, amongst many other things, the HTML layout in scattered dribs and drabs.
To get the Smarty template working, I swapped a chunk of OutputPage::output() into Skin::outputPage(), so the widest pieces of page layout could be done by the template.
I think it'd be a good thing to separate out the functional groups in OutputPage and Skin: wikitext->HTML conversion, RecentChanges layout, history page layout, image upload history layout, HTTP magic, and full-page layout (at the least!).
Skin discussion: http://meta.wikipedia.org/wiki/Skins
General info on Smarty: http://smarty.php.net/
Installation notes: get the Smarty download from the above site (Smart is under LGPL license), untar it, and make sure its "libs" subdirectory is in your PHP include path. Put the *.tpl files into a "templates" directory under the wiki script directory (ie, /w/templates) and make also a templates_c directory writeable by the web server, where it stores the PHP scripts compiled from the templates.
-- brion vibber (brion @ pobox.com)