Осенью 1774 г., исполняя поручение Екатерины II, он провел инспекторскую проверку войск, расположенных в столице и окрестностях, осмотрев полки: Казанский кирасирский, Вологодский и Кексгольмский пехотные. Результатом этой проверки стал рапорт Потемкина, в котором он сделал несколько довольно критических замечаний. Так, например, говоря о Казанском кирасирском полку, Потемкин одобрительно отзывается о состоянии людей, лошадей и амуниции. «Но что принадлежит до тех военных обращений, — продолжает он, — коими оной полк на смотру действовал, то оные от прямого кавалерийского совершенства так удалились, что стремительность и не разлучная нигде с оною стройность, как единственная тяжелой кавалерии сила, без которой ни в малейших пред неприятелем оборотах действовать она не может, в упоминаемом полку вовсе не находится, а тем самым таковой полк ни же с равным числом иррегулярного войска сражаться не может». Здесь Потемкин не просто характеризует состояние полков, но и высказывает программные положения об изменениях в войсках, помня, что против легкой турецкой конницы тяжелая кавалерия уступает. Свои взгляды вице-президент реализовал позднее, когда по его настоянию было увеличено число иррегулярных войск. В этом рапорте Потемкин высказывает и свое отношение к солдатскому быту, его он будет стараться изменить на протяжении всей жизни. Получив одобрительную резолюцию на свой доклад, Потемкин направил 27 октября 1774 г. приказ в Казанский кирасирский полк об исправлении положения: «…А как описываемая мною кавалерийская стремительность приобретается нечувствительным образом посредством прилежания в частых обучениях, то и отношу я оное к господам полковым и эскадронным командирам, дабы они обучали всему выше писанному, избегая сколько можно бесчеловечных и в обычай приведенных к сему побои, творящих службу отвратительную; но ласковым и терпеливым всего истолкованием, узнав твердость, чему они подчиненных обучать обязаны, избегнут случая сами делать нечаянные ошибки и тем приобретут полную их доверенность, любовь и почтение, и превратят службу в почтенное и приятное для них упражнение, исполняя сим как прямую пользу службы, так и человеколюбивое Ее императорского величества намерение».

Этим принципам в организации военного обучения и управления армией Потемкин стремился следовать на посту президента Военной коллегии, постоянно заботясь о подчиненных ему тысячах военнослужащих. В январе 1775 г. Потемкин представил Екатерине II доклад, целью которого было очистить полки «от всех неупотребительных излишностей и каждый род войска поставить на такой ноге совершенства, чтобы вся в нем благопристойность была соответственно стремительному его движению». Он предлагал обучать драгун и конному, и пешему строю, чтобы они могли действовать, не нуждаясь в подкреплении ни пехоты, ни тяжелой конницы.

В том же докладе Потемкин указывал на необходимость увеличить число гусарских полков, нужных для разведывательной службы и быстрых передвижений. На основании соображений Потемкина было сформировано пять драгунских полков (из десяти эскадронов каждый) и семь русских гусарских полков (из шести эскадронов каждый); в 1777 г. при всех кирасирских полках были устроены особые конно-егерские батальоны, а в 1785 г. число гренадер было приказано довести до сорока батальонов и сформировать шесть егерских корпусов (по четыре батальона каждый) и мушкетерские четырехбатальонные полки. Егеря представляли собой отборную пехоту, приученную к рассыпному строю, меткой стрельбе и индивидуальному бою. Они не имели аналогов в иностранных армиях, их слабое подобие можно обнаружить лишь в прусских войсках Фридриха II. Егеря в бою строились в каре и прикрывали фланги, а в случае необходимости разворачивались для стрельбы. В результате произведенного Потемкиным перемещения акцента в пользу легкой кавалерии в русской армии осталось всего 5 кирасирских полков, зато число драгунских было доведено до 10, гусарских — до 16.

Желая создать в среде казачества большую группу своих сторонников и учитывая опыт пугачевского восстания, правительство Екатерины пошло на то, что многие ранее выбранные «на круге» «начальные люди» стали получать патенты на офицерские звания. Эта идея принадлежала Потемкину, который очень высоко оценивал боеспособность казачьих войск и даже призывал солдат и офицеров регулярной кавалерии учиться «сидеть в седле с той свободою, какую казаки имеют». Свое удовольствие казачьими войсками Потемкин высказал в ордере полковнику М. Платову. «Сколь мне было приятно видеть скорые плоды сего вновь учрежденного войска, — писал он в 1788 г., — и сие умножилось видом бодрых воинов, какой они имеют… они уже приобрели осанку, приличную рыцарям». Восхищение Потемкина разделял и союзник России во второй Русско-турецкой войне император Священной Римской империи Иосиф II. В мае 1787 г., путешествуя вместе с императрицей по южным областям России, он делился со своим известным полководцем Ласси наблюдениями по поводу донских казаков: «Ловкость этих людей и род строя, который они умеют соблюдать в самом беспорядке, поистине заинтересовали меня… Если запустить такое войско в тыл расстроившейся кавалерии, она пропала бесповоротно».

Важной задачей для Потемкина на посту президента Военной коллегии стало изменение комплектования армии, особенно в условиях усиления внешнеполитической активности России. Российская регулярная армия со времен Петра I строилась на рекрутских наборах податного населения, Потемкин же впервые распространил рекрутские наборы на Украину и Белоруссию и одновременно ввел новые принципы очередной системы и жеребьевки. В указанных областях был установлен 15-летний срок службы, проведение призыва было ограничено 2 месяцами, население распределялось на части и очереди по 500 человек. Каждая часть имела определенную очередь, внутри которой рекруты призывались по жребию без замены наемниками. Предпринял Потемкин попытку распространить эти принципы на Великороссию, но встретил яростное сопротивление помещиков, что помешало ему завершить проведение рекрутской реформы. Указывая на последствия этой незавершенности, Потемкин писал Екатерине II в конце 1788 г.: «Рекруты отдаваемые слабы и с болезнями, многие застарелыми, так что мрут большим числом, не доходя еще до места. Сколько же их пропадает по непривычке к климату и по крутому приобучению к солдатской жизни и службе, сие ужасно… Термин набора в государстве поставлен толь не вовремя, что рекруты никак на будущую кампанию не поспевают быть солдатами…» Уже в ходе второй Русско-турецкой войны 1787–1791 гг. Потемкин пришел к мнению, что необходимо заменить существовавшую тогда бессрочную службу на срочную. Для прекращения частых побегов солдат в Польшу Потемкин «пехоте и кирасирам порцию отпустить приказал, чем и прекратилось, сказав, что государынина воля сделать после войны срочную службу». Об этом он сообщал в письме к графу А.А. Безбородко и добавлял: «Сие больше всего подействовало. Поляки подманивают. Ей нужно срок положить, хотя б начав с государственных (крестьян. — Н.Б.)». Это прогрессивное для своего времени предложение избавить солдат от изнурительной службы до смерти или инвалидности могло привести не только к пользе частной, но и армия стала бы более молодой и боеспособной. В дальнейшем в России была введена срочная служба.

Необходимость усовершенствований в принципах рекрутского набора признавал и один из ближайших советников Екатерины II А.А. Безбородко, обращаясь к Потемкину: «Весьма желательно было бы, чтоб для пользы государства и вернейшей его обороны план Ваш о службе военной произведен был в действо и чтоб, хотя по окончании войны, сие сделалось». В ходе реформ русской конницы, проведенной Потемкиным в 1783–1786 гг., поселенные полки были преобразованы в полевые, что, несомненно, укрепило вооруженные силы накануне войны.