I'm not so sure I agree with teh google search box as a "must" - its a matter of personal oppinion, and what you've decided you want your users to have.

For me - Simplicity is key. Unclutter, get rid of everything that is not essential or that doesn't DO something useful. A few other no-brainers:

-snap cursor to the natural first input box in a set of forms. Nothing worse than extra mouse clicks.
-have your logo link home.
-absolutely no dead links
-only one (max two) adsense blocks per page