Coal powered cruisers should -from a historical perspective- go in between frigates and oil powered destroyers. The lack of a bombard between trebuchets and cannons is another irritation of mine.
A lot of folks talk about the resources needed... guess I'll add what resources are required with the units I added...
After Frigates, Ships of the Line and Galleons, this is what I did:
Age of Steam:
Ironclad Gunboat (same as default Ironclad... coastal only) - Coal
Ironclad Cruiser (ocean going... light/fast) - Coal
Ironclad Battleship (ocean going... heavy/slow) - Coal
Paddle Steamer (Age of Steam transport) - Coal
Industrial Age:
Protected Cruiser (light/fast) - Coal
Pre-Dreadnought (heavy/slow) - Coal
Transport (now Liberty Class vessel) - Coal/Oil
WWI era:
Destroyer Escort (light/fast) - Coal/Oil
Dreadnought (heavy/slow) - Coal/Oil
Getting back to default Civ4, you then finally progress to what we already have...
WWII era:
Destroyer (light/fast) - Oil
Battleship (heavy/slow) - Oil