Though I've critisized Pappocom on some issues -- mainly the labeling of puzzles beyond a certain level as "invalid" or "arguably unfair" -- his software is one of the best choices for the mainstream. Many newspapers use his puzzles. If you missed it, his software is available for purchase on this very website. $15, with a 28 day trial.
If you want puzzles at skill levels far beyond what you'll ever find in a newspaper and/or you want advanced solving aids and/or easier import and export, try:
Simple Sudoku, free
Sadman Sudoku $12
Sudoku Susser Free