Well I've poked around some, and the quick way to do this would be to replace the getimagethumb() and getdefaultsizedimage() in cache-images.php with the custom size functions for each. Then using the same custom functions with the same parameters in album.php and image.php and they would benefit from the pre-cache, i think.....hope....
Hard way: make some checkboxes in the theme options section that say "size by height?", store these in some new fields in the db, throw some conditionals into the getdefaultsizedimage functions etc, make i.php obey and probably 100 other things im not considering and voila...but yeah consider this a feature request :-)