Как правильно оформить сделку

Нотариус не обязателен.
можно и два договора дарения (но абсолютно безусловных и не зависящих друг от друга)
а можно и договор мены. но при мене есть два нюанса (которые отсутствуют при дарении)
1)обязательно соблюдение первоочередного права покупки (мена в этом приравнивается к купле-продаже) сосбственниками оставшихся долей в обоих квартирах. то есть вам придется либо брать от них нотариальные отказы либо (если они не хотят это сделать добровольно) -посылать всем уведомления
2) супруги меняющихся (если они есть) в любом случае будут иметь право на половину полученных долей.
при дарении есть тоже один нюанс-если дарители и одаряемые не совсем близкие родственники (не супруг, дети, родители, сестры-братья, дедушки-бабушки и внуки-внучки) -тогда им обоим светит налог в 13 % от стоимости дара.
вот и выбирайте, что вам удобнее и выгоднее в вашей ситуации