Yes in fact, that's exactly how the latest version of Market Theme operates.
In the download center is a BETA version of Market Theme 4.0. This improves over the previous version of Market with a category image thumbnail grid navigation system (as you describe above) and more intuitive layout.
You won't have to tweak any code, however you'll probably want to modify the stock colors a little bit. (stylesheet stuff)
This "Beta" version should turn into a full release in probably just a couple of weeks.
I hope this helps.