Speed looks pretty good to me. It can always be fine tuned later though.

Can Reuben drown?

Though making swimming look better should really only affect it when Reuben's in water (just run the swimming code when you're standing in water), and even then i doubt it'd take up much processing time. Unless you'd be writing a masked sprite routine instead of XORing the sprite over top of the water, but even then drawing one masked sprite to the screen won't affect much

I also think Reuben's speed is fine, it looks more like a running speed so you could have a walking speed if you want, but i generally prefer the character to move faster than slower.

Seeing your progress with Reuben is making me want to dust some of my old projects off

Actually to be fair, Reuben in not-swallow water was intended to be walking not swimming, hence the speed being identical. Granted, in real life, walking in water is slower, but I used Zelda Ocarina of Time as reference for the water in Reuben 2.

Also in your bestiary Sorunome, the gold is missing I believe.

I might be able to do 4-lv grayscale sprites at one point, but the issue is that the color set I got right now has some differences, so some sprites will end up being different. Also, the color version of Golem is much larger than in this game.