With medium-sized sprites, 16 angles is all you need to get fluid rotation and you can easily pre-process that. Apart from that you might want to consider using hardware acceleration.
If you absolutely have/want to use GDI, try doing it with scanlines and assembler. Might even work in real-time.