Re: GDI+ Performance Issue
There is a limit to how much graphics you can do without the graphics card. Eventually, you will hit that limit if your graphics get complicated enough. I encountered that limit on one program. The drawing was not going to be fast enough, so I tried a variety of things. The first step was to time everything so that I only focused on the parts that were actually a problem, rather than just the ones I thought could be problems. You seem to have already done that step, though.
Once I had the key points identified, I optimized them as much as I could, but that will never do more than a few percent improvements. In my case, there was an obvious improvement because I could cache all the images that were being drawn. The big issue I ran into was that I had up to a few hundred items being drawn, and the user could zoom in and out, which could result in those few hundred items all being composed and drawn. Since that wasn't fast enough, I cached all the images at each zoom level such that I only had to redraw the ones that had changed at any time. This was fast, but only worked as long as there weren't more than a handful that had to be redrawn at any point in time. The drawback was that, if I ever had to redraw everything, it was FAR slower. At first, that didn't matter to me, because I rarely had to redraw everything. Once I found that there were too many times when I did have to, the whole approach fell apart.
At that point, I switched to XNA, which was a framework that made use of the graphics card. Naturally, MS abandoned XNA a few months later, but it lives on in the MonoGame framework.
My point is that no matter what you do to try to improve the performance with GDI, considering the complexity of the graphics, you will almost certainly exceed what the CPU is capable of, and will need to make use of the graphics card. That doesn't mean abandoning the language, though, as MonoGame will do it, and is .NET. The other option would be WPF, which also uses the graphics card, but that is likely to be a bigger step than MonoGame.
Re: GDI+ Performance Issue
This kind of thing should be done on a GPU. The method you're using is utilizing the CPU to perform those transformations. You need to use a library like DirectX or OpenGL which can perform operations on triangles using the graphic adapter's GPU. Graphics operations tend to be highly parallelizable and GPUs excel at parallel operations.