Well basically if you take heavier strings you will get a higher tension. That usually means that the strings won't 'vibrate' as much and the neck will be bent a bit more. You have to be aware though that this also might mess with the intonation of the guitar - usually they are set up for the gauge you are using...going from 9 to 10 might work though (I have done this for a while on my Gibson Nighthawk).
It will change the way the guitar feels - but if it needs to be quick an dirty maybe try raising the action instead. In any case you won't get around changing the frets.
I agree about at liest leveling and dressing first (unless you can get the complete fret job for a REALLY good price.
Also, dont forget to check the truss rod adlustment and nut slot height too. If the nut slots are too deep it could cause the same problems you are experiencing. (and if they are to high you have to use a c-clamp to play )