Good binary file editor recommendations?

[rhatsaruck]

I need the following features:

MS-DOS compatible that can run from machine booted using Win 98 SE DOS bootdisk
Performs edits in-place
Full screen editing - not command line
Find/Search feature
Able to edit files of any size (disk based editor is OK)
Display ASCII, octal, hexadecimal
Small and fast

Nice to have features:
Windows compatibility
Runs in Windows 9X or later DOS box

Any recommendations? Any programs to avoid?