Aufenthaltsbewilligung, hat sich ergeben:
A.- Die Schweizerin P._ lernte 1994 auf einer Neuseelandreise die geschiedene neuseeländisch-britische Doppelbürgerin C._ kennen. Aus der Beziehung entwickelte sich eine gleichgeschlechtliche Partnerschaft. Anfangs Februar 1995 kehrte P._ in die Schweiz zurück, um ihre Studien in chinesischer Akupressur abzuschliessen, wobei C._ sie hier von Mai bis Juli 1995 besuchte. Nach Abschluss ihrer Ausbildung zog P._ im September 1995 nach Christchurch (Neuseeland), wo sie während 20 Monaten mit C._ zusammenlebte. Die ungünstigen Berufsaussichten am neuen Ort und die schlechte Gesundheit ihrer Mutter bewogen sie, im April 1997 in die Schweiz zurückzukehren, wo sie in Zürich eine Teilzeitstelle fand und eine selbständige Praxis für Akupressurtherapie aufzubauen begann. C._ lebte während der ausländerrechtlich bewilligungsfreien Zeiträume jeweils mit ihr zusammen; die übrige Zeit verbrachte sie hauptsächlich bei ihrem Sohn in Grossbritannien.
B.- Am 24. April 1998 wies die Fremdenpolizei des Kantons Zürich ein Gesuch von C._ ab, ihr eine Einreise- und Aufenthaltsbewilligung zur erwerbslosen Wohnsitznahme bei ihrer Lebenspartnerin und zur Stellensuche zu erteilen. Der Regierungsrat des Kantons Zürich bestätigte diesen Entscheid auf Rekurs hin am 11. November 1998. Hiergegen gelangten P._ und C._ erfolglos an das Verwaltungsgericht des Kantons Zürich. Dieses trat am 16. Juni 1999 auf ihre Eingabe zwar ein, wies die Beschwerde im Rahmen der Interessenabwägung nach Art. 8 Ziff. 2 EMRK jedoch ab, da die Gesuchstellerinnen ihre Beziehung in zumutbarer Weise im Ausland leben könnten. Ihr Wunsch, in der Schweiz zu bleiben, habe hinter dem erheblichen öffentlichen Interesse am Schutz des Landes vor Überfremdung zurückzutreten. Eine Minderheit des Gerichts hätte die Beschwerde indessen gutheissen wollen, da ihr das öffentliche Interesse an der Verweigerung der Bewilligung weniger gewichtig erschien als die den Gesuchstellerinnen zugemuteten Einschränkungen.
C.- P._ und C._ haben hiergegen am 27. September 1999 beim Bundesgericht Verwaltungsgerichtsbeschwerde eingereicht mit dem Antrag, den Entscheid des Verwaltungsgerichts (bzw. des Regierungsrats und der Fremdenpolizei) aufzuheben und die kantonalen Behörden anzuweisen, C._ die Aufenthaltsbewilligung zu erteilen.
Das Verwaltungsgericht beantragt, die Beschwerde abzuweisen, soweit darauf einzutreten sei. Die Direktion für Soziales und Sicherheit sowie der Regierungsrat des Kantons Zürich stellen den Antrag, auf die Beschwerde nicht einzutreten bzw. eventuell sie abzuweisen. Nach Ansicht des Bundesamts für Ausländerfragen ist auf die Beschwerde nicht einzutreten.

Das Bundesgericht zieht in Erwägung:
1.- Nach Art. 100 Abs. 1 lit. b Ziff. 3 OG ist die Verwaltungsgerichtsbeschwerde auf dem Gebiet der Fremdenpolizei ausgeschlossen gegen die Erteilung oder Verweigerung von Bewilligungen, auf die das Bundesrecht keinen Anspruch einräumt. Gemäss Art. 4 des Bundesgesetzes vom 26. März 1931 über Aufenthalt und Niederlassung der Ausländer (ANAG; SR 142. 20) entscheidet die zuständige Behörde, im Rahmen der gesetzlichen Vorschriften und der Verträge mit dem Ausland, nach freiem Ermessen über die Bewilligung von Aufenthalt und Niederlassung. Damit besteht kein Anspruch auf Erteilung einer Bewilligung, es sei denn, der Ausländer oder seine in der Schweiz lebenden Angehörigen könnten sich hierfür auf eine Sondernorm des Bundesrechts oder eines Staatsvertrags berufen (<ref-ruling> E. 1a S. 83; <ref-ruling> E. 2a S. 291, 361 E. 1a S. 363 f.; <ref-ruling> E. 1a, 289 E. 1a, 385 E. 1a; <ref-ruling> E. 1a; je mit Hinweisen).
2.- a) Vorliegend fällt insofern einzig Art. 8 Ziff. 1 der Konvention vom 4. November 1950 zum Schutze der Menschenrechte und Grundfreiheiten (EMRK, SR 0.101) in Betracht. Art. 8 EMRK - wie seit dem 1. Januar 2000 auch <ref-law> - gewährleistet das Recht auf Achtung des Privat- und Familienlebens. Darauf kann sich im Rahmen eines ausländerrechtlichen Bewilligungsverfahrens berufen, wer nahe Verwandte mit einem gefestigten Anwesenheitsrecht in der Schweiz hat. Wird in einem solchen Fall der Aufenthalt untersagt, kann dies Art. 8 EMRK (bzw. <ref-law>) verletzen. Soweit eine familiäre Beziehung tatsächlich gelebt wird und intakt ist, wird das der zuständigen Behörde in Art. 4 ANAG grundsätzlich eingeräumte freie Ermessen beschränkt. Die Verwaltungsgerichtsbeschwerde des um die fremdenpolizeiliche Bewilligung nachsuchenden Ausländers oder seiner hier anwesenden Angehörigen ist unter diesen Umständen deshalb zulässig (<ref-ruling> S. 185 ff.; <ref-ruling> E. 1b S. 364; <ref-ruling> E. 1e S. 5, 289 E. 1c S. 292; <ref-ruling> E. 1d S. 3, 16 E. 3a S. 21, 257 E. 1c S. 259 f.; mit Hinweisen).
b) Das Bundesgericht hat es bisher abgelehnt, diesen Anspruch auf Partner gleichgeschlechtlicher Beziehungen auszudehnen (Urteil des Bundesgerichts vom 22. Mai 1992 i.S. R., publiziert in EuGRZ 1993 S. 537 ff.). Gleichgeschlechtliche Paare könnten sich - so die Rechtsprechung - nicht auf den Anspruch auf Achtung ihres Familienlebens berufen, auch wenn die Konventionsorgane diesen Begriff evolutiv auslegten. Gleichgeschlechtliche Beziehungen bildeten nach gemeineuropäischer Rechtsüberzeugung noch kein Familienleben im Sinne der Konvention. Auch das Recht auf Achtung des Privatlebens und das Grundrecht der persönlichen Freiheit räumten gleichgeschlechtlichen Partnern keinen Anspruch auf Erteilung einer fremdenpolizeilichen Bewilligung ein. Zwar gehörten die Sexualität und das partnerschaftliche Leben zu zweit zu den elementaren Erscheinungsformen der Persönlichkeitsentfaltung, und dies unabhängig davon, ob sich die sexuelle Orientierung auf das gleiche oder auf das andere Geschlecht beziehe. Eingriffe in das Recht auf Achtung des Privatlebens homosexueller Paare seien deshalb vorstellbar; doch sei hiervon die Frage zu unterscheiden, ob der Anspruch auf Achtung des Privatlebens auch berührt werde, wenn eine gleichgeschlechtliche Lebensgemeinschaft aufgrund fremdenpolizeilicher Massnahmen lediglich nicht in einem bestimmten Staat gelebt werden könne. Die Europäische Menschenrechtskonvention regle an sich den Aufenthalt von Ausländern nicht, und es falle auch nicht in den Schutzbereich des verfassungsmässigen Rechts auf persönliche Freiheit, seinen Aufenthalt über Landesgrenzen hinweg frei wählen zu können. Soweit das Bundesgericht entschieden habe, dass sich ausnahmsweise dennoch aus Art. 8 EMRK ein Anspruch auf Bewilligungserteilung ergeben könne, wenn anders eine familiäre Beziehung beeinträchtigt werde, so beruhe dies auf einer Wertentscheidung zugunsten von Ehe und Familie, wie sie auch der im Zivilgesetzbuch getroffenen Regelung der Beziehungen zwischen Frau und Mann in der Ehe zugrunde liege. Ein vergleichbarer Anlass, den fremdenpolizeilichen Grundsatz des freien Ermessens bei der Erteilung von Aufenthaltsbewilligungen einzuschränken, bestehe bei gleichgeschlechtlichen Beziehungen nicht. Aus der persönlichen Freiheit und dem Schutz der Privatsphäre ergebe sich somit ebenfalls kein grundrechtlicher Anspruch auf Erteilung der Bewilligung im Sinne von Art. 100 Abs. 1 lit. b Ziff. 3 OG.
3.- Diese Rechtsprechung ist gestützt auf die seit dem damaligen Entscheid geänderten gesellschaftlichen Verhältnisse zu überdenken: Die rechtliche Erfassung gleichgeschlechtlicher Partnerschaften hat sich seit 1992 entscheidend fortentwickelt. So verabschiedete das Europäische Parlament am 8. Februar 1994 eine "Resolution über die Rechtsgleichheit der Homosexuellen und Lesben in der europäischen Gemeinschaft", welche die Mitgliedstaaten namentlich auffordert, die ungleiche Behandlung von Personen mit gleichgeschlechtlicher Orientierung in den Rechts- und Verwaltungsvorschriften zu beenden. In gleiche Richtung geht der am 25. Februar 2000 im Rahmen des Europarats vorgelegte Bericht "Situation des gays et des lesbiennes et de leurs partenaires en matière d'asile et d'immigration dans les Etats membres du Conseil de l'Europe" (Commission des migrations, des réfugiés et de la démographie, Doc. 8654). Sodann haben neben Dänemark inzwischen auch Norwegen, Schweden, Island und die Niederlande Gesetze erlassen, welche die Registrierung gleichgeschlechtlicher Partnerschaften vorsehen und dieser teilweise eheähnliche Wirkungen zukommen lassen (vgl. den Bericht des Bundesamts für Justiz vom Juni 1999 über die "Rechtliche Situation gleichgeschlechtlicher Paare im schweizerischen Recht", Probleme und Lösungsansätze, S. 7 ff.; Kees Waaldijk, The Legal Situation in the Member States, in: Waaldijk/Clapham: Homosexuality: A European Community Issue, Dordrecht 1993, S. 75 - 129; Pieter van Dijk, The Treatment of Homosexuals under the European Convention on Human Rights, in: Waaldijk/Clapham, a.a.O., S. 179 - 206; Bea Verschraegen, Gleichgeschlechtliche "Ehen", Focus Bd. 9, Wien 1994, S. 107 ff.). In Frankreich wurde im November 1999 das Gesetz über den "pacte civil de solidarité" publiziert, der sowohl homo- wie heterosexuelle Konkubinatspaare erfasst (J.O. no. 265 du 16 novembre 1999 pag. 16959; Loi no 99-944 du 15 novembre 1999 relative au pacte civil de solidarité [1]). In verschiedenen anderen Staaten stehen ähnliche Gesetzesvorschläge zur Diskussion; so unter anderem in Deutschland, Österreich, aber auch der Schweiz, wo der Nationalrat am 27. September 1999 einer von Jean-Michel Gros eingereichten parlamentarischen Initiative entsprochen hat, die es zwei Personen, welche ein dauerhaftes Zusammenleben beabsichtigen, erlauben soll, ihre Partnerschaft registrieren zu lassen (Amtl. Bull. 1999 N 1821 ff.). Ein Vorstoss von Nationalrätin Ruth Genner, wonach gleichgeschlechtlichen Paaren die Möglichkeit eingeräumt werden sollte, eine Ehe einzugehen, wurde dagegen am 20. Dezember 1999 relativ deutlich verworfen (Amtl. Bull. 1999 N 2583 ff.).
4.- a) Diese Entwicklungen lassen - entgegen den Vorbringen der Beschwerdeführerinnen - den Schluss zwar noch nicht zu, dass sich heute eine gemeineuropäische Rechtsüberzeugung in dem Sinne herausgebildet hätte, dass gleichgeschlechtliche Beziehungen unter den Begriff des Familienlebens im Sinne von Art. 8 EMRK bzw. <ref-law> fielen (vgl. hierzu E. 4b); sie berühren jedoch, wie das Verwaltungsgericht zu Recht ausgeführt hat, unter gewissen Voraussetzungen den Schutzbereich des Privatlebens derart, dass die Verweigerung einer Aufenthaltsbewilligung die entsprechende Garantie von Art. 8 Ziff. 1 EMRK verletzen kann, weshalb im Rahmen von Art. 100 Abs. 1 lit. b Ziff. 3 OG ein das Ermessen der Bewilligungsbehörden beschränkender Anspruch nicht mehr generell zu verneinen ist (vgl. hierzu E. 4c).
b) aa) Die in einzelnen Staaten bestehende Möglichkeit, homosexuelle Partnerschaften mit mehr oder weniger eheähnlichen Wirkungen registrieren zu lassen (Ausschluss der Heirat als solcher, unterschiedliche Rechtsstellung hinsichtlich der Möglichkeit von Adoptionen, Ausschluss von der medizinisch unterstützten Fortpflanzung usw. ), hat nichts daran geändert, dass das Institut der Ehe, das gemeinhin den Kern der familiären Beziehungen darstellt und sowohl konventions- wie verfassungsrechtlich nach wie vor besonderen Schutz geniesst (vgl. Art. 12 EMRK, <ref-law>, Art. 54 Abs. 1 aBV), ausschliesslich heterosexuellen Paaren offen steht (vgl. die Urteile des Europäischen Gerichtshofs für Menschenrechte vom 17. Oktober 1986 i.S. Rees und vom 26. September 1990 i.S. Cossey, Série A, vol. 106 bzw. 184, bestätigt im Urteil vom 30. Juli 1998 i.S. Sheffield [Heiratsmöglichkeit von Transsexuellen]; Urteil des Gerichtshofs der Europäischen Gemeinschaften vom 17. Februar 1998 i.S. Grant [Rechtssache C-249/96]; Urteil des deutschen Bundesverfassungsgerichts vom 4. Oktober 1993, publiziert in: NJW 1993 S. 3058 f.). Auch wenn der rechtliche Status gleichgeschlechtlicher Partner in verschiedenen Rechtsbereichen im Sinne einer Beseitigung ungerechtfertigter Diskriminierungen verbessert worden ist, kann doch nicht von einer generellen Gleichstellung mit der Ehe bzw. einer entsprechenden Ausdehnung des traditionellen Familienbegriffs gesprochen werden. Die Ehe und Familie trägt aus biologischen Gründen immer noch und natürlicherweise in anderer Form zum Fortbestand der Gesellschaft bei als die gleichgeschlechtliche Partnerschaft. Mit Doktrin und Rechtsprechung ist deshalb daran festzuhalten, dass homosexuelle Beziehungen nicht unter den Schutzbereich des in Art. 8 EMRK gewährleisteten Rechts auf Achtung des Familienlebens, sondern unter jenen des Privatlebens fallen (vgl. Martina Caroni, Privat- und Familienleben zwischen Menschenrecht und Migration, Berlin 1999, S. 35 f. mit weiteren Hinweisen, differenzierend S. 175 f., S. 309 ff; Bernhard Pulver, Unverheiratete Paare, Basel/Genf/München 2000, S. 30 mit kritischer Würdigung auf S. 46; Mark E. Villiger, Handbuch der Europäischen Menschenrechtskonvention [EMRK], 2. Aufl. , Zürich 1999, Rz. 571, S. 365; Haefliger/Schürmann, Die Europäische Menschenrechtskonvention und die Schweiz, Bern 1999, S. 314 f. u. S. 318/319; Hausmann/Hohloch, Das Recht der nichtehelichen Lebensgemeinschaft, Berlin 1999, S. 550 Rz. 31; Frowein/ Peukert, Europäische Menschenrechtskonvention, EMRK-Kommentar, 2. Aufl. , Kehl/Strassburg/Arlington 1996, Rz. 2 zu Art. 12 und Rz. 15 zu Art. 8; Wildhaber, Internationaler Kommentar zur Europäischen Menschenrechtskonvention, Rzn. 144, 151, 342 zu Art. 8). Zwar verzichten die Strassburger Organe zusehends auf eine strenge Abgrenzung zwischen Familien- und Privatleben und prüfen jeweils die Einhaltung eines "kombinierten" Schutzbereichs (vgl. Stephan Breitenmoser, Das Recht auf Achtung des Privat- und Familienlebens in der Schweizer Rechtsprechung zum Ausländerrecht, in: EuGRZ 1993 S. 537 ff., insbesondere S. 542; Hanspeter Mock, Le droit au respect de la vie privée et familiale, du domicile et de la correspondance [art. 8 CEDH] à l'aube du XXIe siècle, in: RUDH 1998 S. 237 ff.; derselbe, Mesures de police des étrangers et respect de la vie privée et familiale, in: ZSR 112/1993 I S. 95 ff., insbesondere S. 97 f.; Van Dijk, a.a.O., S. 191 ff.); im Zusammenhang mit dem hier umstrittenen Anspruch auf die erstmalige Erteilung einer fremdenpolizeilichen Bewilligung ist die Unterscheidung aber nach wie vor von Bedeutung (vgl. Van Dijk, a.a.O., S. 185 III. ; auch Wildhaber, a.a.O., Rzn. 150 FN 16 u. 151). Den berechtigten Anliegen gleichgeschlechtlicher Paare kann im Rahmen des Anspruchs auf Schutz ihres Privatlebens Rechnung getragen werden.
bb) Nichts anderes ergibt sich aus dem schweizerischen Verfassungsrecht: Nach vorherrschender Auffassung gehen Art. 54 Abs. 1 aBV bzw. <ref-law> von einem traditionellen Verständnis der Ehe als einer auf Dauer angelegten, umfassenden Lebensgemeinschaft zwischen zwei Menschen unterschiedlichen Geschlechts aus (<ref-ruling> E. 4; Detlev Ch. Dicke, in: Kommentar zur Bundesverfassung der Schweizerischen Eidgenossenschaft vom 29. Mai 1874, Rz. 1 zu Art. 54; differenzierend Jörg Paul Müller, Grundrechte in der Schweiz [im Weitern: Grundrechte], Bern 1999, S. 102 f.); der Ehebegriff umfasst nicht auch die gleichgeschlechtliche Partnerschaft (<ref-ruling> ff.; Bericht des Bundesamts für Justiz vom Juni 1999, S. 62 f.; Müller, a.a.O., Grundrechte, S. 104; Auer/Malinverni/Hottelier, Droit constitutionnel suisse, Bd. 2, Les droits fondamentaux, Bern 2000, Rz. 364/365). Art. 54 Abs. 1 aBV bzw. <ref-law> gewährleisten die Ehe als Rechtsinstitut in diesem - traditionellen - Sinn (<ref-ruling> E. 4b S. 267). Hiervon ist auch der Bundesrat in seiner Botschaft vom 20. November 1996 zur neuen Bundesverfassung ausgegangen, wenn er dort festhielt, dass das Recht auf Ehe - mit dem der Begriff der Familie kulturgeschichtlich wie rechtlich verknüpft ist (vgl. Dicke, a.a.O., Rz. 2 - 4; Auer/Malinverni/Hottelier, a.a.O., Rz. 360) - sich auf die Verbindung von Frau und Mann bezieht, ohne auch "Ehen" zwischen transsexuellen oder homosexuellen Partnern zu erfassen; die Ausweitung auf alle Formen des Zusammenlebens widerspräche - so der Bundesrat - dem Grundgedanken des Instituts der Ehe (BBl 1997 I 154 f.). Diese Auffassung blieb in den Verfassungsberatungen unbestritten (Bericht des Bundesamts für Justiz vom Juni 1999, S. 62), weshalb die Beschwerdeführerinnen aus der Ehefreiheit bzw. deren angeblich diskriminierender Handhabung nichts zur ihren Gunsten abzuleiten vermögen (vgl. zur Diskriminierungsproblematik <ref-ruling> E. 6 S. 216 ff.; <ref-ruling> E. 3; bei gemischtgeschlechtlichen Paaren: Pulver, a.a.O., S. 41 f.).
c) aa) Wie das Bundesgericht im bereits zitierten Entscheid von 1992 dargelegt hat, fallen gleichgeschlechtliche Beziehungen indessen unter das Recht auf Achtung des Privatlebens. Zwar hat es daraus in seiner Rechtsprechung bisher keinen eigentlichen Anspruch auf eine Anwesenheitsbewilligung abgeleitet. In BGE <ref-ruling>6 E. 3b S. 22 hielt es fest, ein solcher fiele höchstens dann in Betracht, wenn besonders intensive private Beziehungen in Frage stünden, was es damals wie in späteren Fällen indessen jeweils verneinte (unveröffentlichte Urteile vom 31. August 1994 i.S. F., E. 3c; vom 3. November 1994 i.S. S., E. 2b; vom 23. Dezember 1997 i.S. Q., E. 2c; vom 11. August 1998 i.S. E., E. 5; und vom 31. Januar 2000 i.S. S., E. 4). Auf diese Rechtsprechung, die an sich zu bestätigen ist, kann im vorliegenden Zusammenhang indessen nicht unbesehen abgestellt werden, ging es dabei doch jeweils lediglich um übliche soziale Beziehungen, wie sie der Ausländer normalerweise während eines längeren Aufenthaltes in der Schweiz im Rahmen seiner allgemeinen Integration zu knüpfen pflegt. Die Beziehungen zwischen homosexuellen Partnern, die in einer stabilisierten Gemeinschaft leben, denen das Institut der Ehe jedoch nicht offen steht, um ihre Beziehung - analog der Regelung in Art. 7 bzw. Art. 17 ANAG für gemischtgeschlechtliche Partner - gestützt auf einen nationalrechtlichen Bewilligungsanspruch über die Grenzen hinweg verwirklichen zu können, sind im Vergleich hierzu intensiver. Wird ihnen die Bewilligung verweigert, kann dies den Schutzbereich des Rechts auf Privatleben in einer Art und Weise berühren, welche die Verweigerung der Bewilligung für ein partnerschaftliches Zusammenleben einem direkten staatlichen Eingriff gleichkommen lässt. In solchen Fällen ist das Recht auf Achtung des Privatlebens deshalb geeignet, im Sinne von Art. 100 Abs. 1 lit. b Ziff. 3 OG einen Bewilligungsanspruch zu begründen (vgl. Van Dijk, a.a.O., S. 190 ff.; Caroni, a.a.O., S. 309 ff.; Breitenmoser, a.a.O., S. 543 f.; Mock, a.a.O., ZSR 112/1993 I S. 98; Wildhaber, a.a.O., N 150 FN 16; Müller, Grundrechte, a.a.O., S. 104); dies auch mit Blick darauf, dass nach Art. 14 in Verbindung mit Art. 8 EMRK bzw. <ref-law> niemand wegen seiner Lebensform diskriminiert werden soll, worunter auch die Homosexualität fällt (vgl. Jörg Paul Müller, Die Diskriminierungsverbote nach Art. 8 Abs. 2 der neuen Bundesverfassung, in: Die neue Bundesverfassung, Konsequenzen für Praxis und Wissenschaft, Bern 2000, S. 122; derselbe, Grundrechte, a.a.O., S. 426).
bb) Wie generell in der Rechtsprechung zu Art. 8 EMRK genügt aber auch bei einer gleichgeschlechtlichen Partnerschaft das blosse Behaupten einer Beziehung nicht, um den Bewilligungsanspruch auszulösen und das Ermessen der Behörden im Rahmen von Art. 4 ANAG zu beschränken. Art. 8 EMRK (bzw. der inhaltlich gleichwertige <ref-law>; BBl 1997 I 152 ff.; Müller, Grundrechte, a.a.O., S. 43) garantiert kein absolutes Recht auf Aufenthalt in einem Konventionsstaat in dem Sinn, dass eine Pflicht bestünde, Nichtstaatsangehörigen die Einreise oder eine Aufenthaltsbewilligung oder -verlängerung zu gewähren bzw. die Wahl ihres Wohnsitzes zu respektieren (<ref-ruling> E. 3a; <ref-ruling> E. 3a S. 640, mit Hinweisen; Mock, a.a.O., in: RUDH 10/1998, S. 242). Von einem Eingriff in das Privatleben kann bei der Verweigerung einer erstmaligen Bewilligung zum Vornherein nur dann die Rede sein, wenn überhaupt eine Beeinträchtigung von einer gewissen Schwere zur Diskussion steht, was ein qualifiziertes Verhältnis voraussetzt. Wie hinsichtlich des Familienlebens im Sinne von Art. 8 Ziff. 1 EMRK muss eine nahe, echte und tatsächlich gelebte Beziehung bestehen, damit der über ein gefestigtes Anwesenheitsrecht verfügende Ausländer oder Schweizer bzw. sein gleichgeschlechtlicher ausländischer Partner sich für die Bewilligungserteilung auf Art. 8 EMRK bzw. 13 Abs. 1 BV berufen kann (Caroni, a.a.O., S. 481; Breitenmoser, a.a.O., S. 541 f.; Pulver, a.a.O., S. 43). Unter welchen Voraussetzungen das Vorliegen einer solchen Beziehung zu bejahen ist, muss aufgrund der Umstände im Einzelfall beurteilt werden. Dabei spielt die bisherige Dauer der Beziehung bzw. des gemeinsamen Haushalts eine zentrale Rolle; daneben ist die Intensität der Partnerschaft aufgrund zusätzlicher Faktoren - wie etwa der Art und des Umfangs einer vertraglichen Übernahme gegenseitiger Fürsorgepflichten, des Integrationswillens und der Integrationsfähigkeit bzw. der Akzeptanz in den jeweiligen Familien und im Bekannten- bzw. Freundeskreis der Betroffenen - zu belegen (vgl. den Bericht des Bundesamts für Justiz vom Juni 1999, S. 54).
cc) Nicht entscheidend ist in diesem Zusammenhang - entgegen dem Urteil aus dem Jahre 1992 (EuGRZ 1993 S. 562 ff.) -, ob die Beziehung allenfalls andernorts gelebt werden kann. Dieser Umstand schränkt den Geltungsbereich des Schutzes des Privatlebens nicht ein (vgl. Caroni, a.a.O., S. 309 ff.; Van Dijk, a.a.O., S. 185 ff.). Die faktische Möglichkeit des hier über ein gefestigtes Anwesenheitsrecht verfügenden Ausländers oder Schweizers, seinem Partner ins Ausland zu folgen, berührt den Anwendungsbereich von Art. 8 Ziff. 1 EMRK bzw. <ref-law> als solchen nicht; es handelt sich dabei um einen (unter mehreren) im Rahmen der Interessenabwägung nach Art. 8 Ziff. 2 EMRK mitzuberücksichtigenden Aspekt ("connections approach" statt "elsewhere approach" bzw. Schranken- statt Eingriffsproblematik: Breitenmoser, a.a.O., S. 542 ff.; Caroni, a.a.O., S. 310 f.; Wildhaber, a.a.O., Rz. 453 f. zu Art. 8 EMRK; Mock, a.a.O., in: RUDH 1998 S. 246; Van Dijk, a.a.O., S. 192). Im Rahmen der Rechtfertigungsgründe sind alle Umstände des zu beurteilenden Falles zu berücksichtigen. Hierzu gehört die Tatsache, dass in den meisten Staaten - selbst in solchen, in denen inzwischen das gleichgeschlechtliche Konkubinat einen rechtlichen Rahmen erhalten hat - kein voraussetzungsloses "Nachzugsrecht" besteht (vgl. etwa Art. 12 des französischen Gesetzes "relative au pacte civil de solidarité") ebenso wie die Frage, ob und wieweit gleichgeschlechtliche Partner im anderen für sie allenfalls in Frage kommenden Staat gerade wegen ihrer sexuellen Neigung verfolgt oder diskriminiert würden (vgl. Caroni, a.a.O., S. 481). Im Rahmen der Interessenabwägung von Art. 8 Ziff. 2 EMRK sind sämtliche objektiven und subjektiven Momente des Verlassens des bisherigen Aufenthaltsorts und des Beziehungsumfelds einerseits und die am neuen Ort bestehenden Assimilierungs- und Integrationsmöglichkeiten bzw. -schwierigkeiten andererseits gegeneinander und im Vergleich zu allenfalls entgegenstehenden öffentlichen Interessen abzuwägen (vgl. Breitenmoser, a.a.O., S. 544).
d) Die Beschwerdeführerinnen lernten sich im Jahre 1994 in Neuseeland kennen; ihre Beziehung ist nahe, echt und wird trotz aller Schwierigkeiten tatsächlich gelebt. Sie besteht nunmehr bereits seit annähernd sechs Jahren, wobei eine wechselseitige Integration der Partnerinnen sowohl in Neuseeland wie im Rahmen des bewilligungsfrei möglichen Aufenthalts in der Schweiz erfolgt ist. Unter diesen Umständen beeinträchtigt die Verweigerung der beantragten Bewilligung - wie das Verwaltungsgericht zu Recht festgestellt hat - ihr Recht auf Privatleben im Sinne von Art. 8 EMRK, weshalb auf ihre Verwaltungsgerichtsbeschwerde einzutreten und zu prüfen ist, ob die Verweigerung der erstmaligen Erteilung der Aufenthaltsbewilligung gerechtfertigt erscheint.
5.- a) Nach Art. 8 Ziff. 2 EMRK ist ein Eingriff in das nach Ziffer 1 geschützte Rechtsgut statthaft, soweit er gesetzlich vorgesehen ist und eine Massnahme darstellt, die in einer demokratischen Gesellschaft für die nationale Sicherheit, die öffentliche Ruhe und Ordnung, das wirtschaftliche Wohl des Landes, die Verteidigung der Ordnung und zur Verhinderung von strafbaren Handlungen, zum Schutze der Gesundheit und Moral sowie der Rechte und Freiheiten anderer notwendig erscheint. Nichts anderes ergibt sich aus <ref-law>, wonach jede Beschränkung eines verfassungsmässigen Rechts grundsätzlich einer gesetzlichen Grundlage bedarf (Abs. 1), im öffentlichen Interesse liegen muss (Abs. 2) und mit Bezug auf das erstrebte Ziel nicht unverhältnismässig sein darf (Abs. 3); der Kernbereich des Rechts ist auf jeden Fall zu wahren (Abs. 4). Im vorliegenden Zusammenhang decken sich die Eingriffsvoraussetzungen von Art. 8 Ziff. 2 EMRK und <ref-law> (vgl. Villiger, a.a.O., Rzn. 551 ff. u. 579).
b) aa) Die Verweigerung der Anwesenheitsbewilligung an die Beschwerdeführerin 2 stützt sich auf die gesetzliche Ordnung, namentlich Art. 4 ANAG, und verfügt somit über eine hinreichende gesetzliche Grundlage (vgl. BGE <ref-ruling> E. 3a S. 6; Pulver, a.a.O., S. 43). Diese ist entgegen der Ansicht der Beschwerdeführerinnen genügend bestimmt. Das den Behörden dort eingeräumte Ermessen ist unter Beachtung der gesamten Ordnung des Ausländerrechts auszuüben, namentlich der Bestimmungen über den Familiennachzug in Art. 7 Abs. 1 und Art. 17 Abs. 2 ANAG bzw. Art. 8 EMRK (<ref-law>) sowie der bundesrätlichen Verordnung vom 6. Oktober 1986 über die Begrenzung der Zahl der Ausländer (BVO; SR 823. 21). Art. 8 EMRK verbietet nicht, die Einwanderung und den Zugang zum Staatsgebiet zu regeln und an gewisse Bedingungen zu knüpfen; er vermittelt - wie bereits dargelegt - kein absolutes Recht auf Einreise. Das schweizerische Ausländerrecht beruht für das Bundesgericht verbindlich (vgl. Art. 114bis aBV bzw. <ref-law>) auf dem Grundsatz, dass - gesetzliche oder konventionsrechtlich gebotene Ausnahmen vorbehalten - kein Anspruch auf eine Bewilligung des Aufenthalts besteht. Gestützt hierauf ist Art. 4 ANAG - zusammen mit der veröffentlichten und allgemein zugänglichen Rechtsprechung des Bundesgerichts - hinreichend klar gefasst (vgl. Villiger, a.a.O., Rzn. 547 u. 579).
bb) Die im vorliegenden Zusammenhang zu beurteilende Zulassungsbeschränkung dient dem Schutz des Landes vor Überfremdung sowie der Erhaltung des Gleichgewichts auf dem inländischen Arbeitsmarkt. Art. 4 ANAG bzw. die Begrenzungsverordnung dienen der Aufrechterhaltung eines ausgewogenen Verhältnisses zwischen dem Bestand der schweizerischen und dem der ausländischen Wohnbevölkerung, der Schaffung günstiger Rahmenbedingungen für die Eingliederung der hier wohnenden und arbeitenden Ausländer sowie der Verbesserung der Arbeitsmarktstruktur und einer möglichst ausgeglichenen Beschäftigung (Art. 1 BVO). Die im Rahmen des ausländerrechtlichen Bewilligungssystems zu prüfende Ermessenshandhabung der kantonalen Behörden bezweckt die Sicherung der öffentlichen Ruhe und Ordnung sowie des wirtschaftlichen Wohls des Landes und damit auch der hier bereits anwesenden Ausländer. Diese Interessen sind unter dem Gesichtswinkel von Art. 8 Ziff. 2 EMRK legitim (BGE <ref-ruling> E. 3a S. 6 f.; <ref-ruling> E. 3b S. 4 f., 22 E. 4a S. 24 f.; <ref-ruling> E. 4b; <ref-ruling> E. 2d S. 161).
c) Heikel mag vorliegend die Verhältnismässigkeit der Massnahme erscheinen, sprechen doch unbestrittenermassen keine polizeilichen Gründe gegen die Erteilung der beantragten Bewilligung. Dennoch überwiegen die öffentlichen Interessen die geltend gemachten privaten, weshalb der angefochtene Entscheid vor dem Recht auf Schutz des Privatlebens standhält:
aa) Die Beschwerdeführerinnen lebten von September 1995 an während 20 Monaten in Neuseeland, wo sie sich kennen gelernt haben, in einem gemeinsamen Haushalt. Im April 1997 kehrte die Beschwerdeführerin 1 in die Schweiz zurück, wobei ihre Partnerin ihr insofern nachfolgte, als sie sich hier jeweils während der bewilligungsfreien Zeit - d.h. sechs Monate pro Jahr - aufhielt. Nach unbestrittener Feststellung im angefochtenen Entscheid sind die beiden nach der Abweisung ihres Rekurses durch den Regierungsrat wieder nach Neuseeland zurückgekehrt, wobei ihnen dies offenbar keine grösseren Schwierigkeiten bot. Auch wenn diese Ausreise unfreiwillig erfolgte, haben die Beschwerdeführerinnen ihr Privatleben damit doch bereits zuvor schwergewichtig im Ausland gepflegt. Beide Beschwerdeführerinnen haben sich im Heimatstaat der jeweiligen Partnerin um Integration bemüht und sind - soweit ersichtlich - auch von den jeweiligen Familien akzeptiert worden. Unter diesen Umständen berührt die Wahl des Aufenthaltsorts so oder anders das Privatleben einer der beiden Partnerinnen stärker als jenes der anderen.
bb) Wohl würde es die Beschwerdeführerin 1 vorziehen, mit ihrer Partnerin in der Schweiz zu wohnen, weil ihre Berufsaussichten hier offenbar günstiger sind und sie so die Beziehungen zu ihrer im Kanton Graubünden lebenden, kranken Mutter einfacher pflegen könnte. Dies ändert indessen nichts daran, dass es für die Beschwerdeführerinnen sowohl zumutbar wie rechtlich möglich ist, ihre Beziehung - wie bisher - entweder im Rahmen des bewilligungsfrei möglichen Aufenthalts in der Schweiz oder dauerhaft in Neuseeland zu leben, zumal sie trotz Pflegebedürftigkeit der Mutter nach Abweisung ihres Rekurses dorthin zurückgekehrt sind und bereits zuvor in Christchurch gelebt haben. Gemeinsame Besuche in der Schweiz sind - wenn auch distanzmässig erschwert - rechtlich wie tatsächlich nicht ausgeschlossen, womit die Beziehungen zur Familie der Beschwerdeführerin 1 und ihrem Bekanntenkreis nicht nur über Post, Telefon und Internet, sondern auch persönlich gepflegt werden können. Irgendwelche weiteren spezifischen Gründe, welche die Verlegung des Aufenthalts, abgesehen von den bereits dargelegten persönlichen Präferenzen, in die Schweiz nahelegen oder gebieten würden, machen die Beschwerdeführerinnen nicht geltend und sind auch nicht ersichtlich. Unter diesen Umständen haben die kantonalen Instanzen ihr Ermessen weder konventions- noch bundesrechtswidrig gehandhabt (vgl. Art. 104 lit. a OG), wenn sie davon ausgingen, der mit der Verweigerung der Bewilligung verbundene Eingriff in das Privatleben der Beschwerdeführerinnen sei gestützt auf Art. 8 Ziff. 2 EMRK gerechtfertigt. Ob und inwiefern der Entscheid über die Verhältnismässigkeit der Massnahme hinaus, welche das Gericht frei prüft (<ref-ruling> E. 1b S. 116, mit Hinweisen), auch angemessen (opportun) erscheint, ist der gerichtlichen Kontrolle entzogen (vgl. Art. 104 lit. c OG).
cc) Es ist in erster Linie am Gesetzgeber, im Rahmen einer demokratischen und pluralistischen Auseinandersetzung darüber zu befinden, inwiefern und unter welchen Kautelen es sich im Rahmen der Ausländer- und Einwanderungspolitik rechtfertigt, gleichgeschlechtlich orientierten Personen einen Bewilligungsanspruch einzuräumen, da ihnen anders als den gemischtgeschlechtlichen Konkubinatspartnern das Institut der Ehe aufgrund des geltenden Rechts nicht offen steht. Die entsprechenden Gesetzgebungsarbeiten sind im Gange. Das Bundesgericht hat, soweit möglich, deren Inhalt nicht vorwegzunehmen; es muss sich (vorerst) auf eine diskriminierungsfreie, durch die Strassburger Rechtsprechung getragene Wahrung der Rechte Homosexueller im Rahmen von Art. 8 EMRK (bzw. <ref-law>) beschränken. Dabei ist der Tatsache Rechnung zu tragen, dass in Fällen wie dem vorliegenden Verfahrensgegenstand nicht eine Entfernungs- oder Fernhaltemassnahme bildet (Ausweisung, Nichterneuerung einer Aufenthaltsbewilligung), welche mit Blick auf die Integration nicht nur des ausländischen Partners, sondern auch des Konkubinats als solchem unter dem Gesichtswinkel der Verhältnismässigkeit allenfalls andere Fragen aufwirft als die Erteilung einer erstmaligen Bewilligung.
dd) Vor diesem Hintergrund ist der Einwand der Beschwerdeführerinnen zu relativieren, die Erteilung der Bewilligung im konkreten Fall erscheine kaum geeignet, die Ausgeglichenheit des Verhältnisses zwischen der einheimischen und der ausländischen Wohnbevölkerung bzw. des Arbeitsmarkts in Frage zu stellen. Die Kritik übersieht, dass die Einwanderungspolitik als solche immer mit gewissen Härten verbunden ist, die für sich allein einen Staat noch nicht verpflichten, von Konventions oder Verfassungs wegen auf eine solche zu verzichten.
6.- a) Nach dem Gesagten ist auf die Verwaltungsgerichtsbeschwerde zwar einzutreten, weshalb nicht weiter geprüft werden muss, ob und inwiefern sie andernfalls als staatsrechtliche Beschwerde entgegenzunehmen wäre. In der Sache selber ist sie jedoch abzuweisen, weil der Eingriff in den Schutzbereich des Privatlebens der beiden Beschwerdeführerinnen im Sinne von Art. 8 Ziff. 2 EMRK gerechtfertigt erscheint. Art. 8 in Verbindung mit Art. 14 EMRK bzw. Art. 13 Abs. 1 in Verbindung mit <ref-law> verankern keine Pflicht zur Erteilung einer Aufenthaltsbewilligung für gleichgeschlechtliche Partner unterschiedlicher Nationalität, soweit eine Fortführung der Beziehung - wie hier - am bisherigen Wohnort möglich und zumutbar erscheint.
b) Dem Verfahrensausgang entsprechend werden die unterliegenden Beschwerdeführerinnen kostenpflichtig (Art. 156 Abs. 1 in Verbindung mit Art. 153 und Art. 153a OG). Eine Parteientschädigung ist nicht geschuldet (Art. 159 OG). Dass eine Minderheit des Verwaltungsgerichts die Beschwerde gutgeheissen hätte, rechtfertigt diesbezüglich keine andere Beurteilung. Das Gleiche gilt für die mit dem vorliegenden Entscheid verbundene Praxisänderung hinsichtlich des Art. 100 Abs. 1 lit. b Ziff. 3 OG. Das Bundesgericht bestätigt mit seinem Entscheid im Ergebnis vollumfassend - wenn auch mit Nuancen in der Begründung - das angefochtene Urteil des Verwaltungsgerichts; die Beschwerdeführerinnen konnten sich deshalb nicht in guten Treuen im Sinne von Art. 159 Abs. 3 OG zur Prozessführung veranlasst sehen.

Demnach erkennt das Bundesgericht:
1.- Die Verwaltungsgerichtsbeschwerde wird abgewiesen.
2.- Die Gerichtsgebühr von Fr. 2'500. -- wird den Beschwerdeführerinnen unter solidarischer Haftbarkeit auferlegt.
3.- Es wird keine Parteientschädigung zugesprochen.
4.- Dieses Urteil wird den Beschwerdeführerinnen, der Direktion für Soziales und Sicherheit, dem Regierungsrat und dem Verwaltungsgericht (2. Kammer) des Kantons Zürich sowie dem Eidgenössischen Justiz- und Polizeidepartement (Bundesamt für Ausländerfragen) schriftlich mitgeteilt.
_
Lausanne, 25. August 2000
Im Namen der II. öffentlichrechtlichen Abteilung
des SCHWEIZERISCHEN BUNDESGERICHTS
Der Präsident:
Der Gerichtsschreiber: