Looks like you got all your information down pretty well. Since you're willing to start a new character, there's no need to try to convince you. That's probably the best option. I'd recommend going for one of the explorer classes, since you can't screw up your skills by not doing quests and such and such, and it'll give you a good feel for something at least a little familiar to what you're used to.
It's true that it's ridiculously easy to level, now. With a good series of anime, a few energy drinks and a weekend, it's easy to get past third job. If you're looking for populated worlds, Scania is probably the way to go. Always the most popular world. An alternative would be my home server, Windia. I'm willing to help you out in-game if you were to play Windia, although I don't play that much. Feel free to ask on the forums if you need anything, I'm sure people will answer what they can.
If you're looking for places to train, PhazonKirby (Lex) has an excellent, albeit slightly outdated guide for levelling. It should still be reasonably accurate.
In any case, the best way to get back into the game is to just take it easy. Don't try to level up as quickly as you can, take your time and absorb all the information. Compared to back when Pirates came out, it's almost a whole new game. Good luck!