• Tiny 4-bit CPU with 4-bit input and output ports. Like the #TD4 CPU but a bit more capable.
• Connect the output port to a SSD1306-style OLED display. These can be driven via SPI which would be simple enough.
• Have it do something non-trivial - I love the TD4 for its simplicity, but can a slightly more capable CPU do something more interesting? How about finding prime numbers, or displaying a fractal?
• 256 words of RAM is plenty. It will have to be a Harvard architecture with a considerably bigger program ROM - 4Kx8 sounds good. Instructions would be 8 bits wide.
• As few ICs as possible. The TD4 has 12 chips, but can only run very small programs. This Brainfuck machine has 14 chips and can run non-trivial programs, but you need to be a wizard to write programs for it. Let's see what can be done with less than 20. Instruction decoding can be done with the help of diodes.

If we're going to write characters to the display we need a font, which is a lot of constant data. The easiest thing is for that constant data to reside in ROM in the form of instructions, which populate RAM:

    lda %1011    ; load accumulator with 4 bits
    sta $1       ; store at some memory location (upper 4 address bits will come from somewhere else)
    lda %0101    ; next 4 bits
    sta $2
    ...

 The next part of the program then reads the data in RAM and clocks it out serially.

Control flow: we will have something simple like "jump if accumulator is zero". Is this enough? Can you have subroutines when you can only jump to an immediate address? Maybe if you have a jump table at the end of each subroutine, selecting which caller to jump back to.

Addressing: similar question - can all addresses be immediate, or do we need the ability to store addresses in RAM?

There will be many tradeoffs to look at - if removing a couple of chips causes the code size to balloon to make up for it, it may not be worth it.