Попробую детально ответить.
- автоматический поиск родственников по базам в интернете,
Такого в России нигде нет. Если Ваша родня с территории, похожей на территорию РФ сейчас, базы данных не будет.
- русский интерфейс, красивая и понятная графика,
Наиболее русская программа это Древо Жизни, хорошо русифицирован Gramps, MH, Geni. Но графика из этих трех наиболее нормальная в MH. Можете рассмотреть программы для Mac.
- неограниченное число фотографий (у нас много старых фотоальбомов),
Для работы с фото нет нормального инструментария ни у одной из программ. Старые альбомы если осканировать, убрать на долгое хранение оригиналы, то из оцифрованных фото можно делать фотокниги. Можно хранить их в любом облачном сервисе для фото. Можно конечно использовать любые генеалогические программы, в частности Gramps, Древо Жизни, MH, Geni. Но это имеет смысл пожалуй только если Вы используете онлайн программу, и рассчитываете, что фото будут интересны дальней родне. В принципе большие объёмы старых фото, не разобранные по небольшим коллекциям мало кому интересны... А вот выставленные в фотокниги, в календари, это другое.
- надёжность хранения информации (утечки не волнуют, но хочется оставить это древо детям), чтобы сохранилось "на века",
Только печать плаката, фотокниги. Программа это база данных, привязанная к технологиям, которые устаревают.
- дешевле MyHeritage, если найдётся сервис, удовлетворяющий всем остальным пожеланиям, то можно и заплатить.
В основном у нас все дешевле чем MH. Если платить, то соглашусь с другим ответом, Geni имеет больше преимуществ.