I agree that you should choose scheme #2, but with the following proviso:
I'm imagining that you're using this for a news aggregation page with links to each news item and maybe a bit of the first paragraph. This would mean that the variable you're passing has to do with pagination, and not the ID of the news item.
If you're using this scheme for news items, what you should really be doing is something more like /news/man-bites-dog/ or /news/paris-hilton-did-something/ -- basically, lowercase your headline and join it with a dash. It may mean you'll have to have unique news story titles and you'll have to look them up by name rather than an indexed ID, but if you're actually worried about search optimization, the slight performance decrease is nothing compared to the strength of the text you're optimizing for in your URL.