The required maximum is $n$. The following example shows that $N$ cannot exceed $n$. Split the $n$ airports in the $i$-th state, $i = 1, \dots, p$, into $p$ disjoint groups of $n/p$ airports each, $A_{i,j}$, $j = 1, \dots, p$. Let the $k$-th air company, $k = 1, \dots, p$, operate direct flights between every airport in $A_{i,j}$ and every airport in $A_{i',j'}$ if $i \neq i'$ and $j' - j \equiv k(i' - i) \pmod{p}$, and operate no flights between the airports in $A_{i,j}$ and those in $A_{i',j'}$ otherwise.

Since $p$ is prime, for every $i \neq i'$ and every $j, j'$, there exists $1 \le k \le p$ satisfying the previous congruence modulo $p$, so every two airports in different states are connected by a flight. On the other hand, for any given $k = 1, \dots, p$, the $np$ airports are split into $p$ disjoint $n$-element groups, namely, $\bigsqcup_{i=1}^p A_{i,j+ki}$, $j = 1, \dots, p$ (the indices are reduced modulo $p$), such that there are no flights between different groups operated by the $k$-th air company. Consequently, $N \le n$.