You cannot compare a DOS COM program to an ELF binary, though.

The ELF header alone is 64 bytes while COM files have no header and can fit more than a Hello World program into 64 bytes (uncompressed):

  mov ah,9
  mov dx,108
  int 21
  ret
  db "Hello world!$"

Using just debug.com (on DOS) this results in a 21 byte COM executable that prints "Hello world!" to the console. This simply isn't possible with formats like ELF, no matter what the linker does.

Since DOS also allows direct access to video memory, just switching to VGA mode (320x200, 8-bit colours, e.g. using mov ax,13h; int 10h) will allow you to create fancy graphics with just a few bytes. In fact, I can get a colour pattern on the screen, wait for a key press, and return to text mode in just 45 bytes (for use with debug.com):

  a 100
  mov ax,13
  int 10
  mov ax,a000
  mov es,ax
  xor di,di
  xor ax,ax
  mov cx,fa00
  mov es:[di],al
  inc ax
  inc di
  dec cx
  jnz 111
  mov ax,0600
  mov dx,ff
  int 21
  jz  119
  mov ax,3
  int 10
  mov ax,4c00
  int 21

  n vgademo.com
  rbx
  0
  rcx
  2D
  w
  q

This should work on any DOS machine and in DOSBox (I used VDos to create the COM file since I don't have a DOS assembler installed, and debug.com is included in vDOS) and is smaller than just an ELF header :D

Those are impressive but it's not really a fair comparison, 256 byte intros are typically DOS executables which only require a handful of bytes worth of boilerplate before you're putting pixels on the screen. The OP is working with Linux executables, which have a much higher fixed overhead to get running nevermind display any graphics, and that's reflected in the smallest category for Linux and Windows intros being 4096 bytes.