I understand that if a block cipher has $k$-bit keys and $n$-bit input/output blocks, then if $k>n$, we can expect one message-ciphertext pair to narrow us down (I think?) to $2^{k-n}$ possible keys, right? But doesn't DES/AES have a similar system as a block cipher with keys bigger than the blocks. So surely finding one message-ciphertext pair doesn't narrow down the key search so much!?
As you can see, I'm quite confused and so any help would be appreciated!
I understand that if a block cipher has $k$-bit keys and $n$-bit input/output blocks, then if $k>n$, we can expect one message-ciphertext pair to narrow us down (I think?) to $2^{k−n}$ possible keys, right?
That is approximately correct (if the block cipher with the wrong key acts like a random permutation; this is generally a safe assumption); if block "one message-ciphertext pair", you mean "a single $n$-bit plaintext/ciphertext block.
However, that's not necessarily what we mean by a "message-ciphertext pair". We often want to encrypt messages that are larger than $n$ bits; to do this, we use a mode of operation (which uses the block cipher to encrypt larger messages); if we have a larger message (and we know the plaintext and the ciphertext of this larger message), then we usually (depending on the exact mode used) have a number of $n$-bit plaintext/ciphertext blocks.
The upshot of this is that if we have a $k$-bit message (and corresponding ciphertext), this is usually sufficient to allow us to recognize the key (with a possible 1 or 2 false hits; those can be eliminated if we take a message slightly larger than $k$ bits); if $k>n$, then we would get several plaintext/ciphertext pairs against the underlying block cipher
You're missing a component : a padding convention. Yes, if you're trying to reduce a block size, it will reduce the cipher strength. That's why the less-sized blocks are padded/filled to fit the exact size. What to do : pad or fill or both - that is a question. First you need to understand, that the more predictible the message, the less secure the transmission of ciphertext : you're aware that it's a TCP packet, for example, and then you KNOW that it has a header e.t.c... So the filling and padding are usually performed both and with the random data, not filling by, for example, zeros. As an example we can say that for cipher AES-256 the first 8 bits will be actual packet size in bits, and if it's less than a full one - 1 = 255, the remainder will be filled equally from the beginning and from an end with random data with the remainder(if any) in a trail. So - AES-256 will receive it's full block and it will not make a reduction you're mentioned, and you'll be able to trim the message data from random-data in a partial package. It's just an example, but I think it will give you the main idea.
