diff --git a/runtime/factories/roaming/roaming.go b/runtime/factories/roaming/roaming.go
index ee9453a..a015e18 100644
--- a/runtime/factories/roaming/roaming.go
+++ b/runtime/factories/roaming/roaming.go
@@ -15,7 +15,6 @@
 
 import (
 	"flag"
-	"net"
 
 	"v.io/x/lib/netconfig"
 	"v.io/x/lib/netstate"
@@ -75,8 +74,9 @@
 
 	lf := commonFlags.ListenFlags()
 	listenSpec := rpc.ListenSpec{
-		Addrs: rpc.ListenAddrs(lf.Addrs),
-		Proxy: lf.Proxy,
+		Addrs:          rpc.ListenAddrs(lf.Addrs),
+		Proxy:          lf.Proxy,
+		AddressChooser: internal.NewAddressChooser(logger.Global()),
 	}
 	reservedDispatcher := debuglib.NewDispatcher(securityflag.NewAuthorizerOrDie())
 
@@ -85,29 +85,6 @@
 		discovery.Close()
 	}
 
-	// Our address is private, so we test for running on GCE and for its
-	// 1:1 NAT configuration.
-	if !internal.HasPublicIP(logger.Global()) {
-		if addr := internal.GCEPublicAddress(logger.Global()); addr != nil {
-			listenSpec.AddressChooser = netstate.AddressChooserFunc(func(string, []net.Addr) ([]net.Addr, error) {
-				// TODO(cnicolaou): the protocol at least should
-				// be configurable, or maybe there's a RuntimeFactory specific
-				// flag to configure both the protocol and address.
-				return []net.Addr{netstate.NewNetAddr("wsh", addr.String())}, nil
-			})
-			runtime, ctx, shutdown, err := rt.Init(ctx, ac, discovery, nil, &listenSpec, nil, "", commonFlags.RuntimeFlags(), reservedDispatcher)
-			if err != nil {
-				ishutdown()
-				return nil, nil, nil, err
-			}
-			runtimeFactoryShutdown := func() {
-				ishutdown()
-				shutdown()
-			}
-			return runtime, ctx, runtimeFactoryShutdown, nil
-		}
-	}
-
 	publisher := pubsub.NewPublisher()
 
 	// Create stream in Init function to avoid a race between any
@@ -136,8 +113,6 @@
 	cleanupCh := make(chan struct{})
 	watcherCh := make(chan struct{})
 
-	listenSpec.AddressChooser = internal.IPAddressChooser{}
-
 	runtime, ctx, shutdown, err := rt.Init(ctx, ac, discovery, nil, &listenSpec, publisher, SettingsStreamName, commonFlags.RuntimeFlags(), reservedDispatcher)
 	if err != nil {
 		ishutdown()
diff --git a/runtime/factories/static/static.go b/runtime/factories/static/static.go
index 939e0e0..01fa2de 100644
--- a/runtime/factories/static/static.go
+++ b/runtime/factories/static/static.go
@@ -7,7 +7,6 @@
 
 import (
 	"flag"
-	"net"
 
 	"v.io/v23"
 	"v.io/v23/context"
@@ -58,44 +57,20 @@
 
 	lf := commonFlags.ListenFlags()
 	listenSpec := rpc.ListenSpec{
-		Addrs: rpc.ListenAddrs(lf.Addrs),
-		Proxy: lf.Proxy,
+		Addrs:          rpc.ListenAddrs(lf.Addrs),
+		Proxy:          lf.Proxy,
+		AddressChooser: internal.NewAddressChooser(logger.Global()),
 	}
 	reservedDispatcher := debuglib.NewDispatcher(securityflag.NewAuthorizerOrDie())
-
 	ishutdown := func() {
 		ac.Shutdown()
 		discovery.Close()
 	}
-
-	// Our address is private, so we test for running on GCE and for its 1:1 NAT
-	// configuration. GCEPublicAddress returns a non-nil addr if we are
-	// running on GCE.
-	if !internal.HasPublicIP(logger.Global()) {
-		if addr := internal.GCEPublicAddress(logger.Global()); addr != nil {
-			listenSpec.AddressChooser = rpc.AddressChooserFunc(func(string, []net.Addr) ([]net.Addr, error) {
-				return []net.Addr{addr}, nil
-			})
-			runtime, ctx, shutdown, err := rt.Init(ctx, ac, discovery, nil, &listenSpec, nil, "", commonFlags.RuntimeFlags(), reservedDispatcher)
-			if err != nil {
-				ishutdown()
-				return nil, nil, nil, err
-			}
-			runtimeFactoryShutdown := func() {
-				ishutdown()
-				shutdown()
-			}
-			return runtime, ctx, runtimeFactoryShutdown, nil
-		}
-	}
-	listenSpec.AddressChooser = internal.IPAddressChooser{}
-
 	runtime, ctx, shutdown, err := rt.Init(ctx, ac, discovery, nil, &listenSpec, nil, "", commonFlags.RuntimeFlags(), reservedDispatcher)
 	if err != nil {
 		ishutdown()
 		return nil, nil, nil, err
 	}
-
 	runtimeFactoryShutdown := func() {
 		ishutdown()
 		shutdown()
diff --git a/runtime/internal/address_chooser.go b/runtime/internal/address_chooser.go
new file mode 100644
index 0000000..500465c
--- /dev/null
+++ b/runtime/internal/address_chooser.go
@@ -0,0 +1,60 @@
+// Copyright 2015 The Vanadium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package internal
+
+import (
+	"net"
+	"sync"
+
+	"v.io/v23/logging"
+	"v.io/v23/rpc"
+)
+
+type addressChooser struct {
+	logger               logging.Logger
+	gcePublicAddressOnce sync.Once
+	gcePublicAddress     net.Addr
+	ipChooser            IPAddressChooser
+}
+
+func (c *addressChooser) setGCEPublicAddress() {
+	c.gcePublicAddressOnce.Do(func() {
+		c.gcePublicAddress = GCEPublicAddress(c.logger)
+	})
+}
+
+func (c *addressChooser) ChooseAddresses(protocol string, candidates []net.Addr) ([]net.Addr, error) {
+	c.setGCEPublicAddress() // Blocks till the address is set
+	if c.gcePublicAddress == nil {
+		return c.ipChooser.ChooseAddresses(protocol, candidates)
+	}
+	return []net.Addr{c.gcePublicAddress}, nil
+}
+
+// NewAddressChooser will return the public IP of process if the process is
+// is being hosted by a cloud service provider (e.g. Google Compute Engine,
+// Amazon EC2), and if not will be the same as IPAddressChooser.
+func NewAddressChooser(logger logging.Logger) rpc.AddressChooser {
+	if HasPublicIP(logger) {
+		return IPAddressChooser{}
+	}
+	// Our address is private, so we test for running on GCE and for its 1:1 NAT
+	// configuration. GCEPublicAddress returns a non-nil addr if we are
+	// running on GCE/AWS.
+	//
+	// GCEPublicAddress can unforunately take up to 1 second to determine that the
+	// external address (see https://github.com/vanadium/issues/issues/776).
+	//
+	// So NewAddressChooser fires it up in a goroutine and returns immediately,
+	// thus avoiding any blockage till the AddressChooser is actually invoked.
+	//
+	// I apologize for the existence of this code! It is ugly, so if you have any
+	// suggestions please do share. Ideally, the operation to "detect whether the
+	// process is running under an Amazon EC2 instance" wouldn't block for a
+	// timeout of 1 second and we can do away with this mess.
+	ret := &addressChooser{logger: logger}
+	go ret.setGCEPublicAddress()
+	return ret
+}