I can't comment on Paint.net but I used GIMP for several years and didn't find the transition to PS to be too difficult. Obviously they're different programs, but the time I spent learning GIMP really helped to flatten the curve in going to PS.
Even after having transfered to PS, I'm still damn inpressed with what GIMP was able to do for free.
If you think you'll ever move to PS (or any other high-end program) it's worth considering which of the available free programs has the more similar interface.