Blood seems to run it's best for me when I play it at 800x600, anything above either flickers or is much slower. Since my screen's resolution is 1920x1200, the 800x600 box (since I play windowed) takes up very little of the screen. I recall running Redneck Rampage at 640x480 and then stretching the resolution to 1280x1024. It did not look any better but the window took up more space on the screen.
Maybe I'm weird for wanting this, but is there any way to stretch the 800x600 resolution to a larger window?

Did you try pressing F4 or Alt+Enter?