NFA for words which start and end with different letters with $O(\log(| \Sigma |))$ states
The original question referred to DFA (and not NFAs). However, no DFA for $L$ with $O(k)$ states exists.
Consider $\Sigma$ as a set of words (i.e., each word consists of a single  character from $\Sigma$).
Given any two distinct words $a,b \in \Sigma$, the word $a$ is a distinguishing extension for $a$ and $b$. I.e., $aa \not\in L$ but $ba \in L$.
This shows that the number of equivalence classes of $L$ w.r.t. the equivalence relation &quot;not having a distinguishing extension&quot; is at least $|\Sigma|$.
By the Myhill-Nerode theorem, any DFA for $L$ must have at least $|\Sigma|$ states.

The idea to build a NFA with $O(k)$ states is as follows:
in addition to an initial state $s$, and to an accepting final state $t$ there are $2k$ states indexed with $1, \dots, 2k$.
Assign a distinct integer $x_a$ from $0$ to $2^k-1$ to each character $a \in \Sigma$ and consider the binary string $b_a$ of length $2k$ obtained by concatenating the binary string of length $k$ representing $x_a$ in binary, with its complement.
For each character $a \in \Sigma$ let $S_a$ be the set of all states $i$ such that the $i$-th least significant bit in $b_a$ is $1$, and define $\overline{S}_a = \{1, \dots, 2k\} \setminus S_a$.
For each $a \in \Sigma$, add the following transitions:

A transition from $s$ to each state $i \in S_a$.
A transition from each state $i \in \{1, \dots, 2k\}$ to itself.
A transition from each state $i \in \overline{S}_a$ to $t$.

Given a word $\sigma_1, \sigma_2, \dots, \sigma_n$ with $\sigma_1 \neq \sigma_n$, let $i$ be an index such that the $i$-th least significant bit of $b_{\sigma_1}$ is $1$  while the  $i$-th least significant bit of $b_{\sigma_n}$ is $0$ (such an index always exists).
Then, $s \to i \to i \to \dots \to i \to t$ is an accepting path in the NFA.
Conversely, any accepting path is of the form $s \to i \to i \to \dots \to i \to t$ for some $i$. This implies that $i \in S_{\sigma_1} \cap S_{\sigma_n}$, i.e., $b_{\sigma_1}$ and $b_{\sigma_n}$ differ (at least) on the $i$-th least significant bit. This shows that $\sigma_1 \neq \sigma_n$.
The number of states of the NFA is $2k+2$.
Here is an example for $\Sigma = \{x,y,z,w\}$. All edges for which no label is shown are actually labelled with $x,y,z,w$.