Как и когда в западноевропейских армиях появилось деление на подразделения и была введена многоуровневая система званий?

Начать следует с того, что люди Средневековья всё-же никогда полностью об Античности не забывали и периодически пытались её осмыслить. В том числе и античные военные трактаты, суммирующие опыт тех же римлян. Другое дело, что совокупность политических, социальных и экономических условий просто физически не позволяла создать нечто подобное в смысле военной машины. Да и вряд ли было нужно.

Во-вторых, коли Вы сами обозначили в качестве периода Раннее Новое время, то необходимо принять во внимание, что на протяжении львиной части этой эпохи регулярных армий не существовало вовсе. Первопроходцами в этом деле были Нидерланды и Мориц Оранский (вторая половина XVI века), который в своих военных преобразованиях как раз и обратился к античному опыту конструирования вооружённых сил.

Иногда за дату создания регулярных армий принимают формирование французских Ордонансовых рот в конце Столетней войны, которые отныне не собирались по случаю, а несли службу постоянно. Если вкратце, то каждая такая рота состояла из 100 рыцарских копий. Копье - это минимальная тактико-административная единица, включающая 1 тяжеловооруженного рыцаря/жандарма и 3-5 его соратников рангом и качеством пониже. Но это всё же еще не совсем регулярная армия. Скорее это армия "высокоорганизованного Средневековья", проторегулярная армия. Поэтому тут разумнее начинать отсчет всё-таки с Нидерландов, с которых победное шествие регулярности и пошло по миру.

Можно еще вспомнить Пикардийский пехотный полк, созданный во Франции в самом конце XV века, существующий, насколько я помню, до сих пор. И несмотря на то, что полк прошел, фактически, через всю военную историю Франции Нового и Новейшего времени, тогда в XV веке это еще была не регулярная армия.

В-третьих, маленькая неточность содержится в самом вопросе. Полноценная система званий не была введена, а скорее конструировалась на протяжении очень долгого времени. Я бы даже сказал, что она была выстрадана. Вдумайтесь: даже в Наполеоновскую эпоху не произошло ещё чёткого разделения между званием и должностью. Что уж говорить об армиях XVIII, а тем более XVI-XVII веков. Это сейчас у бойца есть звание "рядовой" и есть должность "стрелок". В течение большей части Нового времени это было не так. Сама должность и функции, которые исполняло то или иное лицо, запросто могли заменять звание. Примеров можно приводить массу:

И так далее. Причем это запросто могло и, как правило, различалось в зависимости от рода войск: в пехоте и в кавалерии одно и то же звание называлось по-разному. В нашей армии это дожило до 1917 года, а во французской живо до сих пор. Отвечая на один из Ваших подвопросов, из этого сумбурного изложения можно также понять, что универсальной эта система не была. Современная система нам сейчас видится более-менее универсальной и сбитой, но это скорее результат того, что в конечном итоге европейское военное дело пошло по более-менее единому пути.

В-четвертых, само смысловое наполнение военных терминов было подчас совершенно иным, чем в наше время. Такие слова, как "капитан", "полк", "рота", "бригада", "дивизия", "лейтенант" и прочие для нас сейчас либо абсолютно и бесповоротно устоялись, либо имеют сугубо военное значение. А между тем нужно понимать, что в прошлом и в своих родных языках значение их было сугубо прикладным и повседневным. Я об этом мимоходом упоминал в своем ролике на Цифровой истории.

Капитан происходит от латинского слова Caput - голова. То есть капитан - это дословно "главный".

Лейтенант, как Вы верно заметили - это "заместитель": lieu - место, tenant - держащий.

Весьма интересно о ротах - compagnie.

Слово это тоже пришло из глубины веков. Выше я писал, что ротами назывались в том числе первые проторегулярные подразделения Французского королевства. Но это отнюдь не современные роты: рота ордонансовых жандармов, состоящая из ста копий по 5-6 человек в каждом, составляя по меркам той же Наполеоновской эпохи скорее хороший полнокровный кавалерийский полк в 500-600 всадников. Согласитесь, это не нынешняя рота в среднем в 90-150 бойцов. А командовал-то при этом... капитан, хотя де-факто он командовал целым полком.

Причем это черта сохранялась во Французской армии достаточно долго. Французская тяжелая кавалерия XVII и большей части XVIII веков была представлена т. н. Жандармерией, которая тоже делилась на роты. Но это точно так же были не современные роты, и даже не роты Наполеоновской эпохи. Термин "рота" здесь вполне себе соответствует еще средневековой традиции.

То же самое могло преследовать и термин "Régiment" - полк. Был, например, такой Королевский Карабинерный полк, который полком был лишь по названию и в армии Старого Порядка всегда насчитывал от 1500 до 4000 кавалеристов. По названию полк, а по меркам Наполеоновских войн это полнокровная кав. дивизия.

Словом Division, которое переводится просто "часть/отделённая часть" тоже могли обозначать достаточно разные вещи в разное время. Дивизия в нашем понимании - лишь одно значение. В реальности же слово division могло соответствовать, например, кавалерийскому эскадрону во французской армии XVII века.

Ещё по поводу дивизий. В XVIII веке боевые действия характеризовались довольно низкими интенсивностью, скоростью и напряжением сил. Поэтому для управления небольшими армиями вполне хватало объединений звена полк-бригада. Более крупные объединения - дивизии - присутствовали, но создавались только на время, в течение одной кампании и не имели постоянных командиров. Более-менее постоянного состава дивизии, существующие на продолжительной основе - это изобретение уже опять Наполеоновской эпохи.

Такое ощущение, что я толком ни на что не ответил... Но надеюсь, что хотя бы примерное представление создать получилось...