Can we always find such an irreducible polynomial of degree n where degree(p(x)-x^n)<= n/2? Consider unitary polynomials of degree $n$ over $GF(2)$. That is, polynomials of the form $p(x) = \sum_{i=0}^n a_i x^i$ where $a_i\in GF(2)$ and $a_n=1$. 
Can we always find such an irreducible polynomial $p(x)$ of degree $n$ where $\textrm{degree}(p(x)-x^n)\leq n/2$? 
Example: $p(x)=1+x^2+x^3+x^5+x^{400}$ is an irreducible polynomial where $\textrm{degree}(p(x)-x^n)=5\leq 400/2$.
Further question: If I assume that $n$ is sufficiently large, say $n\geq 32$, is a tighter bound possible (e.g., $\textrm{degree}(p(x)-x^n)\leq n/4$)?
 A: I think (but I could easily be wrong), that this follows, at least for many degrees (in the stronger form also conjectured by Noam and Gjergji) from the results of S. D. Cohen as in 
MR2092633 (2005g:11245) 
Cohen, Stephen D.(4-GLAS)
Primitive polynomials over small fields. Finite fields and applications, 197–214, 
Lecture Notes in Comput. Sci., 2948, Springer, Berlin, 2004. 
11T06 (11T30 11T71) 
If you look at the math review, you will see that he shows that we can find a "primitive" polynomial over $F_q$ (primitive = irreducible AND every root is a primitive root in the appropriate $F_{q^k}.$) with the first $m$ coefficients prescribed if \
$q^{n/2-m} > m W(q^n-1),$ where $W(j)$ denotes the number of square-free divisors of the integer $j.$
A: I suppose this question is the F_2[t] analogue of the question "does the interval [N, N^^{1/2}] always contain a prime?"  After all, you are asking about the set of polynomials at infinity-adic distance less than 2^{n/2} from a fixed polynomial of size 2^n; this is the polynomial version of an "interval."  
This is pretty close to Legendre's conjecture, which is still open.  On the other hand, Cramer proved under RH (which you have in F_2[t] case) that there is always a prime between N and cN^{1/2} log N; so I would see if you can adapt his proof to get the bound you want with the bound n/2 replaced by n/2 + log n.
A: I leave my earlier post below where I mistakenly understood the original problem because of a bad illustrative example given there. Here I only indicate the explicit formula for the number $N_ m(p)$ of monic polynomials of exact degree $m$ irreducible over $GF(p)$:
$$
N_m(p)=\frac1m\sum_{d\mid m}\mu(d)p^{m/d}.
$$
This formula is again from Prasolov's Polynomials, and it seems to be absent in other posts and comments.

I assume that the irreducibility is discussed over $\mathbb Z$, otherwise $x^{400}+x^5+x^2+1$ has zero $x=1$ in $GF(2)$.
Victor Prasolov in Section 8 of his book Polynomials discusses the irreducibility
of trinomials and quadrinomials, mostly based on the work [W. Ljunggren, On the
irreducibility of certain trinomials and quadrinomials, Math. Scand. 8
(1960), 65--70]. One of the results from there is as follows.
Theorem. Let $n\ge2m$, $d=\text{gcd}(n,m)$, $n_1=n/d$ and $m_1=m/d$. Then the
polynomial
$$
g(x)=x^n+\epsilon x^m+\epsilon', \quad\text{where}\ \epsilon,\epsilon'\in\lbrace\pm1\rbrace,
$$
is irreducible except for the following cases in which $n_1+m_1\equiv0\pmod3$:
(a) $n_1$ and $m_1$ are odd and $\epsilon=1$;
(b) $n_1$ is even and $\epsilon'=1$;
(c) $m_1$ is even and $\epsilon=\epsilon'$.
In all three cases (a)--(c), $g(x)$ is a product of a certain irreducible polynomial
and $x^{2d}+\epsilon^m{\epsilon'}^nx^d+1$.
Corollary.
If $n\not\equiv2\pmod3$, then $x^n+x+1$ is irreducible.
If $n\equiv2\pmod3$, then $x^n+x^2+1$ is irreducible.
In other words, there is an irreducible degree $n$ polynomial $g(x)$ of the wanted form such that $\deg(g(x)-x^n)\le2$, and this bound cannot be further improved.
