ИМХО, от него ждали не жесткости, а порядка и той самой стабильности.
А он взял и выиграл войну?

Нет, не спорю, порядка и стабильности тоже ждали, но было ли это ключевым требованием? Вот сейчас многие говорят о т.н. негласном соглашении между обществом (российским) и Путиным, стабильность и какой-то достаток в обмен на покорность.
Порядок был наведен достаточно условно, были приструнены олигархи (одного даже посадили показательно, но я бы не сказал, что процесс над Ходорковским является воплощением порядка), был получен практически полный контроль над основными СМИ. А события в той же станице Кущевской говорят о том, что порядок был своеобразный.
Но после сложных лет советского дефицита и грозовых 90-х общество получило какое-то облегчение и приблизительное понимание, как всё работает. Ну и нефть поперла, а с ней и какие-то деньги. И война в Чечне прекратилась так или иначе.
Как в "Убить дракона" — "он выгнал цыган и при нем началось большое строительство".
Но институционального общества, как того хотели многие и из интеллигенции, и из тогдашнего руководства страны, не получилось. Институты общества и государства все больше подменялись управлением в соответствии с принадлежностью к "вертикали власти".
Но в целом большинство вообще не огорчалось по этому поводу, оно гордилось своим "драконом". Даже когда он оттяпал кусок страны вначале у Грузии, а потом у "братской" Украины.
Я бы не назвал это ни стабильностью, ни порядком. Но есть 89%, которым это нравится, несмотря ни на что.