Traditional BIOS setup interfaces had much simpler user interfaces than you're assuming. They were also written in assembly which allowed for much more compact code than you would think based on the size of applications today. They didn't have "full blown TUIs", most used a simple form interface. On the other hand operating systems like GEOS for the Commodore 64 showed how you could implement a full blown GUI in assembly and have it fit in 64K of RAM and still leave room for applications.
The original IBM PC didn't have a BIOS setup interface. It didn't need one: there was no real-time clock to set, no hard drive interface to configure, and no battery-backed CMOS RAM to store any sort configuration values. It wasn't until the IBM PC/AT that the IBM PC architecture gained these things, but even then there was no BIOS setup interface in the BIOS itself. Instead, if you wanted to changed the BIOS settings you needed to run a special program.
Eventually though, IBM PC clone manufacturers started putting the BIOS setup code in the BIOS. However rather than a full-blown text user-interface (TUI), with various widgets, they used a simple form-based interface. There was a bunch of static text, plus various fields where you could set things like the current time or various hard drive parameters. The arrows keys would select which field to edit, and the number keys and/or the plus (+) and minus (-) keys would change the value. Pressing a key like F10 would save the change configuration values and exit.
Over time BIOSes also got bigger and bigger. The IBM PC/AT reserved 128K space for motherboard ROMs, so BIOSes could easily grow to 128K as necessary. Eventually even that wasn't enough space and BIOSes started using bank switching to allow the BIOS to grow even bigger while still staying inside the 128K (or even 64K) footprint allowed.
However, most of this additional ROM space (now implemented using flash memory) didn't go towards more advanced setup interfaces; mostly it was used to support new features and functionality built into the motherboard. Things like Advanced Power Management, ACPI, USB keyboard and mouse support, more advanced disk interfaces with RAID support, and booting of Ethernet, CD-ROM and various kinds of USB devices all required more and more ROM space. While this meant more options were added to the BIOS setup screens, the basic interface remained the same.
(There was a period where BIOS vendors experimented with crude graphical setup interfaces with mouse support, but this didn't last long. They were basically the old form based interfaces with additional icons, so they weren't really much of an improvement.)
Even though BIOSes got bigger and bigger, they still would've been written mostly in assembly language. Aside from there still being a need to keep the code as small and as efficient as possible, most of this code was run in 16-bit real-mode. By the time BIOSes might have considered using C, 16-bit x86 C compilers were obsolete and no longer being developed. By today's standards they weren't very good code generators and a bit on the buggy side, and they weren't going to get any better.
Since BIOS vendors were just iteratively updating their BIOS implementations, writing everything in assembly wasn't that big a problem. They had a stable base of code, well tested and known to support all the weird quirks that 100% IBM PC compatibility required. Today if you were writing an entire traditional BIOS from scratch, you'd probably use C, but rewriting everything in C would have caused the BIOS vendors more trouble then it would've been worth.
Because of the adoption of UEFI, things are very different today. UEFI-based firmware for PC clones operate mostly in 32-bit (or 64-bit) mode. This has allowed to them to have much more fancy graphical setup interfaces written in C and/or C++ and compiled with modern compilers.