Also es gibt eine kostenlose Variante mit glaube ich zwei Adressbüchern. Das kannst du erstmal testen, d.h in Thunderbird einbinden und auf deinen Endgeräten und ein paar Dummy Kontakte einpflegen.
Es gibt glaube ich auch eine Benutzerverwaltung (wegen Familie), bin aber nicht zu 100% sicher.
Wenn das dann passt, muss du die Sachen aus Google exportieren und nach fruux importieren.
Wegen Kategorien: In TB benötigst du dazu den CategoryManager.
Wegen android App: Die soll recht gut funktionieren. Du kannst aber auch jede andere caldav/carddav app nehmen. IOS unterstützt caldav/carddav nativ.