good points i had not considered. here's 2 that are public-domain:
if you pre-determine your bounding boxes for all model geometry, you might want to take a look at
http://www.magic-software.com/SourceCode.html . the MgcIntr3DBoxBox.cpp source (in the 3D intersection section) would be ideal for you as the 2 boxes can be any size and with any orientation. you would only have to write your own code to traverse through your box pairings. a pretty simple and very small code footprint solution.
the other one is a complete CD library, OPCODE, and is found at
http://www.codercorner.com/Opcode.htm . in dll form its about 1/4 MB (75KB compressed). one thing a library would give you would be faster collision detection since they typically use more intersection tests and also use pre-calculated data structures optimized for quick testing. they also allow for complete flexibility re: model data (same code for different aquariums for instance) and would provide a better set of bounding boxes (better fits) as they calculate the boxes themselves (you just provide the triangles). they also will go down to the triangle/triangle intersection level if you request - which may be used for such things as starting up a fish coral polyp eating animation cycle.
hope these help. i have more if your interested.