Интересно, а почему генерал-лейтенант старше генерал-майора?

Это наименование произошло от французского "lieu tenant". Этот термин возник еще в XV веке и его корни - в латинском словосочетании "lосum tenens". Переводится он, в основном, как "наместник", но самый первоначальный смысл - "тот, кто держит место", заменитель либо заместитель.
То есть тот, кто заменяет командира, когда он отсутствует. Но со временем смысл немного менялся и трансформировался в " тот, кто облечен правом власти от вышестоящего начальства". Ну наместник и есть.

С XV века во французской армии лейтенант - это замначальника какого-нибудь отряда. Изначально к численности отряда привязки не было, это была должность, а не звание. Есть вот такие известные лейтенанты ордонансовых рот - Филипп де Сен-Леже, лейтенант роты Клода де Даммартена, Жан д'Инь, лейтенант роты Питера фон Хагенбаха и Шарль де Батц де Кастельмор, который более известен как д'Артаньян, он тоже служил лейтенантом, и по тогдашним меркам это был очень даже высокий статус.

В русском языке лейтенанты существуют начиная с XVII века. Впервые его упоминание можно встретить в военном трактате 1647 года "Учение и хитрость ратного строения пехотных людей", он был предназначен для служащих "полков иноземного строя". Ну в общем, это было переводом трактата западного военного специалиста Иоганна Якоби фон Вальгаузена "Военное искусство пехоты":
"...А первое я вопрошаю, для чего лютенанта, сиречь порутчика, лютенантом именуют, и откуда то имя пришло лютенант, пофранцузскому языку откуду то прошло, столько именуется ничье место или власть имети. Истолко толкуется, что капитановым местом владети и заступати. Имы то цесарским языком также растворим, лютенант то толкуется, что которой без капитана или без иного урядника место и чином и властью владеет так, как бы он сам тут в лицах."

Хотя в то время в России был больше популярен термин "поручик". А "товарищ" в дореволюционной России с XVIII века означал примерно то же самое, что в польских гусарских хоругвях "заместитель". В литературе XIX века нередко можно встретить выражение вроде "Товарищ министра внутренних дел". Это означало не приятеля этого самого министра, а должностное лицо.

Вот поэтому-то до сих пор генерал-лейтенант старше генерал майора. Генерал-лейтенант в изначальном смысле - заместитель полного генерала.