Woe of me to forget Camino. It still works on Macs as early as 10.4, and it maintains archives of previous releases for your 10.3.9 or earlier Macs, although if you haven't gone to 10.3.9, you may want to go back to OS 9 or run Classic and use the next browser.
Classilla runs on Macs from 8.6 up through all versions of MacOS 9, and runs well in Classic. You are limited to Flash 7 on OS9, but do you really want to use Flash? You probably won't be able to play video anyway. Even better, Classilla is in active development.
As far as I know, older versions of MacOS are out of luck, and old versions of Internet Explorer may be you best choice.