There are loads of improvements in the newest version of Magento themes. I just list some from my point of view. I observed these changes when I started using Magento 1.4 three days ago, but they may exist in the late version of 1.3.x.x already for long.
Everyone knows we should separate presentation from content. Magento does it very well since its first public version. Magento 1.4 just makes separation even better. A theme is about presentation, usually made of two parts, app/design and skin. Compared with skin, app/design part is somehow closer to content. Magento 1.4 themes remove layouts and templates from app/design, which means they are fully rely on css to present different themes. Base/default theme is an exception, but it is a fall-back theme.
In 2-column or 3-column page templates, main column code comes before left/right column. I think it hugely helps SEO. I first saw this kind layout in a Zen-Cart template. Maybe Magento was inspired by it. Under template/page, one-column.phtml was deleted, which saves confusion with 1column.phtml.
The header logo is no longer displayed as a background image, which is a minor change but makes big improvement.
I spent 3 days to re-write my theme to be compliant with Magento 1.4 but I love these changes.