So, during the weekend I implemented sprite rendering to the engine, using the method I described earlier. For z-buffering I'm cheating a bit and only compare the sprite vs wall (or sprite vs sprite) height, instead of the actual distance, as both wall and sprite elements are 64 pixels high. This could lead to some small priority bugs if a sprite is very close to a wall, but that can be remedied by not allowing sprites too close to walls
Regarding performance I haven't done any real measurements yet, but everything was still running nicely with a few sprites on screen.
Next up are all the boring bits like game logic, enemy AI, and so on. Should I maybe start a new thread for that, and only write up any possible graphical ideas and optimizations here?