The "Gray code" is a fast way to produce the integers 0,1,2,..2^p-1 in an order such that each differs from predecessor in exactly 1 bit.
Q1 (easy). Find an anti-Gray code where each differs from predecessor in exactly p-1 bits.
Q2 (not so easy). Find a "mid-gray" code where each differs from predecessor in exactly p/2 bits (p>1 even). Note this is impossible if p is a multiple of 4.
Not so easy to do exactly---but you get a decent approximation by simply running a p-bit block cipher in counter mode.
--you can also get an "approximate solution" much more simply by just repeatedly x = x + C (mod 2^p) where C is an appropriately chosen magic odd constant -- C in binary is ...100010001000100010001 This (and the cipher ploy) both are pretty piss-poor approximations, however. I think my method will have difference-bit-counts in the range p/4 to 3p/4 (?), and the Cipher ploy will usually do worse with some difference-bit-counts as small as O(1) and as large as p-O(1). The good news is, 100%-o(1) fraction of the time, the difference-bit-count will be within p/2 +- O(sqrt(p)*log(p)).