What does "老" in "老虎" and "老鼠" mean
EDIT: Also refer to Aminopterin's answer and Travis Hu's answer for more insights.

After some research, I found two reasonable explanations. But, IMHO, the two should be compiled as the following:

老 is a prefix that is added to make 虎 and 鼠 easier to pronounce; besides, it implies that people respect 虎 and fear 鼠.

The two explanations as follow:

Affix for smooth pronunciation
In the Classical Chinese era, texts were concise and some, if not most, of the words were one-character words. Yet, in colloquial context, people prepended/appended affixes to make the words easier to pronounce. These &quot;new&quot; words then became widely accepted and conventional.
Some common affixes and their associated words:

子(suffix)


獅子、兔子、鴨子、猴子、鏡子、桌子、椅子、房子、筷子、刀子...
lion, rabbit, duck, monkey, mirror, table, chair, house, chopsticks, knife...


老(prefix)


老虎、老鼠、老鷹、老師...
tiger, rat, hawk, teacher...


頭(suffix)


甜頭、苦頭、舌頭、骨頭、石頭、木頭...
sweetness, suffering, tongue, bone, stone, wood...

Affix with connotation
In Chinese, 老, apart from aged/experienced, has the implicit, figurative meaning of respected because people respect elderly so as to comply with the social value. That said, people prepended 老 on the ones they respect. This is why 老虎 and 老師 are named the way they are.
老鼠, on the other hand, has various interpretations. Some state that it fits to literal meaning of 老 – old. According to the Compendium of Materia Medica(本草綱目), a medical book, rats have the longest life span. Such misunderstanding came from the impression that rats have a high
rate of reproduction and have been around people back then for the longest time.
Some argue that the 老 in 老鼠 implies the cunning characteristics of rats. This interpretation can also be applied to 鷹. The rest argue that people chose 老 for 老鼠 to imply their fear toward rats and that rats are not easy to deal with.
As to why 獅 is named 獅子 but not 老獅, the reason is intuitive – to avoid conflicting pronunciation with 老師.