Has anyone tried replacing the message icons (book.gif, etc.) with larger icons? If so, were many changes required to the templates to keep everything aligned properly?

how much larger are you wanting to go? Do you have an example site to check out?

Maybe up to twice the current size. The icons I've been using for UBB.classic are 29x25.

I'm not necessarily going to use larger icons, I'm just considering that as an option. I was just wondering if anyone else had done that, and what changes, if any, they had to make to the templates to accomodate the larger size.

You really shouldn't have to make any changes as long as the icons are within reason. Everything flows around them in postlist and the threads.