I'm glad to report that this morning after updating to Mac OS 10.5.1 the firewall seems to be working as advertised. They dropped the "Block all incoming" moniker and replaced it with "Allow only essential services", which I selected.
Also, I enabled "Stealth Mode" under Advanced.
I then ran some tests from another host to verify that the firewall was up and it seemed to be performing as advertised. I'm pretty interested to see what the "Essential" services are - perhaps I will do some digging soon.
Just for completeness run the following tests from another host on the network:
$ ping hostname
(Should return no replies if stealth is on)
$ nmap hostname
(Should also not return with any open ports)
I disabled my firewall temporarily to scan for some open ports and then tested connections to those ports using telnet after re-enabling the firewall. All results were also positive.
I'm very pleased that this issue has been resolved.