Ideally, the flange would have been installed on top of the finished floor. If you tiled up to the old one, then there's no easy way to do that - it can't just be hanging there in the air, it has to be attached. So, what's under yours?
Slightly out of level is annoying for having a pro reset the flange, but you still should be able to get a good seal. It may require a double wax or extra thick. The waxless should work - wire brush the inside of the pipe to clean any crud out if it isn't clean now. I've used several of those seals and not had any problems. Most plumbers don't like to use them because they cost probably 10x what a wax ring costs, and normally, that works well as it has for decades.