Thanks guys!
What's still the biggest problem is the rotation of the map sprite. If I do it in real time, the game slows to a crawl for big maps, and it jumps like crazy (because of rounding errors in the way AGS rotates a sprite, I assume). I coded my own nearest neighbor sprite rotation, and since rotating a 512x512 sprite 359 times took around ten minutes, I decided to save them as files, hence the big download. The result is what you saw, it's still kinda jumpy, but that's in part because ints and shortcuts in the rendering loop. The rotation itself is actually really smooth.
I'm going to try and use my rotation for a 1024x1024 map, but it's going to take really long (thanks CW for the multi-tasking tip, I totally missed that!)
Let's see how that goes; once the rotated sprites are available, track size shouldn't matter except for Out of Memory errors (which I actually got when I tried a 1024 sprite...)
But, regarding map size: if you can live with the track being a bit pixelated, 512x512 isn't actually that small, as long as you "zoom in" on the track. I've changed the factor so that Mario is smaller in relation to the track, and also a bit slower, and it suddenly seems much wider.