Адмирал никогда не был женат. Мало того, он просто сторонился женщин. Однако, будучи уже в весьма зрелых годах, командующий флотом вдруг сходится с молодой еврейкой Юлией Михайловной (Лилей Мойшевной) из Могилёва. Для того чтобы понять суть происшедшего, обратимся к воспоминаниям современников по данному поводу. Один из них пишет: «Грейг был ужасно застенчив в любовных делах», то есть, надо понимать, не искушён. Этим и воспользовалась молодая, красивая и очень энергичная женщина, полностью подчинив себе старого стеснительного холостяка.
Став гражданской женой адмирала А.С. Грейга, Лея сохранила связи со своей многочисленной еврейской роднёй. Несмотря на декларированный переход в христианство (что до сих пор, впрочем, не доказано), она оставалась ревностной почитательницей Ружинского цадика, регулярно посылала взносы на его содержание и переписывалась с ним. Тот, в свою очередь, в благодарность за щедрые пожертвования не замечал «позорного» в глазах евреев поведения своей подопечной. Супруга адмирала, благодаря заступничеству за евреев, прославилась по всей «черте оседлости» под прозвищем «ди муме Леа».
Энциклопедический словарь «„Николаевцы“ 1789–1999 гг.» даёт следующую информацию о жене Грейга: «Грейг (Сталинская) Юлия Михайловна (1800, г. Могилёв, – 1882, г. Санкт-Петербург), жена А.С. Грейга. Еврейка. Из семьи трактирщика М. Сталинского. В молодости служила в трактире отца. Вышла замуж за офицера польских войск капитана Кульчинского. Вскоре развелась и в 1820 году приехала в г. Николаев с поставками корабельного леса (!!!), выдавая себя за польку. Добилась аудиенции у А.С. Грейга, став со временем его гражданской женой. Будучи хорошо воспитана, зная языки и обладая тонким вкусом и обаянием, постепенно сумела создать в адмиральском доме салон, в который входили в основном молодые офицеры и чиновники ЧФ и Адмиралтейства (братья Дали, К.Х. Кнорре, братья Рогули, П.И. Вавилов, супруги Зонтаг и др.). Со временем Юлии Михайловне удалось привлечь к себе николаевское благородное общество, став законодательницей мод и введя в свой круг влиятельных лиц (Н.Д. Критский, В. Метакса, Ш. Рафалович и др.). Около 1827 года тайно обвенчалась с А.С. Грейгом, что вызвало резкие нападки на адмирала и Ю.М. со стороны некоторых шовинистов и антисемитов (Ф. Вигель, Яцын, М.П. Лазарев и пр.). Обладая сильным характером, Ю.М. оказывала некоторое (!!!) влияние на А.С. Грейга в житейских делах. В Николаеве у Грейгов родилось три сына — Самуил, Иван и Василий и дочь Юлия. После перевода А.С. Грейга в Петербург Ю.М. посвятила свою жизнь устройству карьер и судеб детей, стремясь направить их по финансовой линии. Официально признана женой А.С. Грейга только в 1873 году при открытии памятника адмиралу в Николаеве. В Николаеве, в Диком Саду, на месте, где Александр I любовался видом водных просторов, по распоряжению адмирала была сооружена каменная беседка (проект Р. Кузьмина) под названием „Храм Весты“, которую Грейг посвятил Ю.М в честь рождения первого сына — Самуила».
Историк Анатолий Нойман пишет: «По мере вхождения еврейских купцов в русское общество воспитание девушек в семьях становилось более светским, европейским. Дочь Беньямина Шпеера, выйдя замуж за князя Долгорукова, превратилась не просто в княгиню, но в звезду света. Лия Рафалович-Сталинская, дочка трактирщика, выйдя за адмирала Грейга, сделалась чрезвычайно влиятельной фигурой на Черноморском флоте России. Оставаясь, несмотря на крещение и появление буквы „Ю“ перед именем (Юлия), преданной почитательницей Ружинского цадика, она уже в качестве „тётки Леи“ оказывала заступничество притесняемым евреям. Тут образ „прекрасной еврейки“, и без того тяготеющий к библейским образцам, неизбежно пересекался с историями Эсфири и Юдифи. Заметим, что по причине ли почитания девы Марии, или по ещё каким, антисемитизм куда реже распространяется на женщин, нежели на мужчин».
Известный отечественный мемуарист XIX века Ф.Ф. Вигель писал по этому поводу следующее:
«В Новороссийском краю все знали, что у Грейга есть любовница-жидовка и что мало-помалу, одна за другой, все жены служащих в черноморском флоте начали к ней ездить как бы к законной супруге адмирала. Проезжим она не показывалась, особенно пряталась от Воронцова и людей его окружающих, только не по доброй воле, а по требованию Грейга. Любопытство насчёт этой таинственной женщины было возбуждено до крайности, и оттого узнали в подробности все происшествия её прежней жизни. Так же, как Потоцкая, была она сначала служанкой в жидовской корчме под именем Лии или под простым названием Лейки. Она была красива, ловка и умением нравиться наживала деньги. Когда прелести стали удаляться и доставляемые ими доходы уменьшаться, имела она уже порядочный капитал, с которым и нашла себе жениха, прежних польских войск капитана Кульчинского. Надобно было переменить веру; с принятием св. крещения к прежнему имени Лия прибавила она только литеру „ю“ и сделалась Юлией Михайловной. Через несколько времени, следуя польскому обычаю, она развелась с ним и под предлогом продажи какого-то строевого корабельного леса приехала в Николаев. Ни с кем, кроме главного начальника, не хотела она иметь дела, добилась до свидания с ним, потом до другого и до третьего. Как все люди с чрезмерным самолюбием, которые страшатся неудач, в любовных делах Грейг был ужасно застенчив; она на две трети сократила ему путь к успеху. Ей отменно хотелось выказать своё торжество; из угождения же гордому адмиралу, который стыдился своей слабости, жила она сначала уединённо и ради скуки принимала у себя мелких чиновниц; но скоро весь город или, лучше сказать, весь флот пожелал с нею познакомиться. Она мастерски вела своё дело, не давала чувствовать оков, ею наложенных, и осторожно шла к цели своей, законному браку. Говорили даже, что он совершился и что у неё есть двое детей; тогда не понимаю, зачем было так долго скрывать его.
Оправдываясь в неумышленной нескромности, я слагал вину на слугу, а Юлия Михайловна сказала, что не бранить его, а благодарить должна. Сам же Алексей Самойлович, видя моё учтивое, приветливое, хотя свободное с нею обхождение, начал улыбаться и заставил у себя обедать. В её наружности ничего не было еврейского; кокетством и смелостию она скорее походила на мелкопоместных польских паней, так же, как они, не знала иностранных языков, а с польским выговором хорошо и умно выражалась по-русски. За столом сидел я между нею и адмиралом. Неожиданно с сим последним зашёл у нас разговор довольно сериозный. Речь коснулась до завоевательницы и создательницы Новороссийского края (Екатерины Второй).
На другой день, 27-го, помаленьку я начал сбираться в дорогу, когда явился ко мне курьер с приглашением Алексея Самойловича и Юлии Михайловны пожаловать к ним на вечер, бал и маскарад 28 числа. Мне следовало бы отказаться, во-первых, потому, что это был день кончины отца моего, во-вторых, что я два лишних дня должен был потерять в пути; но мне не хотелось невниманием платить за учтивость, да и любопытство увидеть николаевское общество во всём его блеске взяло верх над долгом. Дней за десять перед тем видел я одесское, но не мог судить о великой разнице между ними, не будучи ни с кем знаком. Мужчины несколько пожилые и степенные, равно как и барыни их, сидели чинно в молчании; барышни же и офицерики плясали без памяти. Масок не было, а только две или три костюмированные кадрили. Женщины были все одеты очень хорошо и прилично по моде, и госпожа Юлия уверяла меня, что она всех выучила одеваться, а что до неё они казались уродами. Сама она, нарядившись будто магдебургской мещанкой, выступила сначала под покрывалом; её вёл под руку адъютант адмирала Вавилов, также одетый немецким ремесленником, который очень забавно передразнивал их и коверкал русский язык. На лице Грейга не было видно ни удовольствия, ни скуки, и он прехладнокровно расхаживал, мало с кем вступая в разговоры. Сильно возбудил во мне удивление своим присутствием один человек в капуцинском платье; он был не наряженный, а настоящий капуцин с бородой, отец Мартин, католический капеллан черноморского флота, который, как мне сказывали после, тайно венчал Грейга с Юлией. Оттого при всех случаях старалась она выставлять его живым доказательством её христианства и законности её брака; только странно было видеть монаха на бале…»