What is the average size of an HTTP request/response header?

From Google's SPDY research project whitepaper

Uncompressed request and response headers. Request headers today vary in size from ~200 bytes to over 2KB. As applications use more cookies and user agents expand features, typical header sizes of 700-800 bytes is common.

The HTTP HEAD response from www.google.com is 823 bytes, as checked just now. This is without any authentication. About half of that is the Set-Cookie header. An easy way to check is the curl command.