But why wouldn't the reaction proceed through this way, which makes more sense? Since the reaction above generates an enolate bearing a negative charge first, making the molecule less stable, whereas the one I proposed is just a straightforward E2 reaction.
Both can occur, but the top drawing allows for easier formation of a "free" electron pair.
In general breaking C-C, C-N, etc. bonds has a rather high activation energy barrier, so the direct E2 is going to be pretty slow. The top diagram basically splits the activation energy barrier into a deprotonation step and an elimination step, making the overall transformation easier.
The negative charge will also be somewhat balanced by the positive charge of the nitrogen. At five bonds apart they aren't going to interact that well, but there's definitely a bit of stabilization there too.