My vote for the best cryptic is the Sat telegraph, they have a GK puzzle as well. Not too sure about the news though, the Sunday Times has a review bit which focuses on news
If you still want to do the crossword you can always pay the subscription and get it on line everyday, that's what I do for the Telegraph and The Times and its really worth it as you have access to all the puzzles all the time and can pick and choose at your leisure.
Have a look at 'The Week' magazine in the newsagents - a bit expensive at first sight perhaps (to judge from the property ads it's aimed at Top Executives who are Too Busy to read the dailies) but the subscripion is cheaper and there's usually an introductory freebie trial offer which you can't lose anything by. I think most of us would agree that the crossword is of an excellent standard, plus a suudoku. Depends on what level of 'tabloid' you're looking to replace...
Weekend FT is pretty good ..they have two puzzles a cryptic and a GK,good news coverage and features and magazine.
Failing that the Telegraph has the cryptic every day plus on Saturdays the GK but you have to buy Mondays paper if you want to match up the shaded clues for their Herculis GK crossword.Good news coverage , features and magazine.