It does seem like older games put more of a priority on boss encounters. Contra is a good example.
I guess if it were me, I would look at Castlevania for some inspiration. A plethora of excellent bosses drawing from mythological sources, both biblical and otherwise.
In terms of unique, original gameplay, it's hard to top the bosses in Metal Gear Solid. Too many good ones to name.
Artistically, an excellent reference for imaginative biblical imagery is the work of Hieronymus Bosch:
http://en.wikipedia.org/wiki/Hieronymus_Bosch
Keep in mind, all of this imagery is public domain. Early Netherlandish paintings in general are a good source for unnerving, beautiful images, many containing explicit religious themes and overtones.
In terms of programming, a simple state machine works fine if you are hearkening after old school pattern based bosses. Make each different behavior state into it's own group, then create a handling group to enable/disable states as you like (with timers, by health, however you want).
P.S. Whoops, just noticed the last three digits of my rep score...maybe you should be wary of my advice... <img src="{SMILIES_PATH}/icon_twisted.gif" alt=":twisted:" title="Twisted Evil"> <img src="{SMILIES_PATH}/icon_mrgreen.gif" alt=":mrgreen:" title="Mr. Green">