What set of house rules could you use to make 5E deadly as all get out while altering as little as possible.
Roll 3d6 in order, for stats. Start at first level. Repeat until someone gets to 2nd.
What makes 5e quickly go from deadly to dudly is the instant death/dying rules. At 1st level, instant death, at - your hps in one blow, can totally happen. At 2nd, it'd be a hard-hitting creature on a crit. It gets less and less likely as your hps balloon, and death saves, also pretty generous, become the primary mechanic.
You could, instead, set death at negative-CON or negative-HD-type or negative-your-1st-level-hps or whatever negative sounds good. And track and heal from negatives instead from 0 & having death saves. Dropped PCs could 'bleed' 1 hp/round or make a death save to avoid bleeding, I suppose.
When those guys made that 4E alternate house ruled deadly encounters thing with the Iron Lich and ect..what did they do?
Increasing the levels of enemies could quickly make things deadly (though not in a fun way, if you figure missing a lot while getting hit on 2 is not fun).
Is it as simple as using 24 hour short rest and week long long rests? To be honest that seems boring but maybe i'm wrong.
No, that shifts pacing, it's nothing much to do with being deadly - having more encounters crammed into a day would have the same effect.
Just how far can we push and pull the system?
Until it's completely unrecognizable, if we want.
What about the other half of things though? How do I streamline character creation so making a new character isn't a chore and much faster? Isn't there a section in the DMG on removing skills and taking it to a ability roll?
Nothing to it, when you decide to call for a check, just call for the stat, and say 'with proficiency' or 'without proficiency' based on Race & Class and whether you feel like it.
Also if you made it 3D6 in order and removed feats it would give characters reasons to love those +2 increases a lot more.
Not opting-into feats also simplifies character building, also, presumably no Variant Humans.
It'd be more work for you, but you could make race & class into a single choice: Fighter(champion), Wizard(lore master), Thief(Rogue) or Cleric(life) is human, Dwarf is a Fighter(Battlerager), Elf a Fighter/Magic-user, Hobbit a fighter/thief, and Gnome an Illusionist/Thief. The multi-classes could have their own class tables that averages out like an evenly-advancing character, rather than actually alternating advancement...
You could extend it to half-elf(Druid), half-orc(Barbarian), half-Infernal(Tiefling Warlock), Half-dragon (Dragonborn Dragon Sorcerer), and half-wit(back around the Human Fighter, again), if people get bored with a lack of choices.