I know most exploits over the internet are opportunistic, but assume an aggressor has a specific target, but no physical access to that target. How do you find the target network or device to begin an attack over the internet? My first thought is social engineering, if the adversary can convince the target to access a resource under the adversary's control, then the adversary can obtain the target's IP address that way. What are some other possibilities?
This is the combination of two stages of penetration testing, known as information gathering and enumeration.
Information gathering is the preliminary process of collecting information about your target. This is often divided into passive (no contact with target) and active (contact with target). It can take many, many forms from social engineering, nameserver enumeration, website research, and more.
Enumeration generally refers to discovering and listing resources within the network, such as servers or user accounts. Typically, this phase occurs after the attacker has already gained access to the network, but in cases where the configuration is poor or data is otherwise leaked, it may be accessible without such a foothold.
If the target is a known company you might be able to see if there are vulnerabilities on it's website, and you can use that to get some public facing IP's, but you'd have to make sure it's not a rented hosting service. A reverse 'whois' might also help you figure out what IP's the target owns, unless they mask their info. Otherwise I'm not 100% how else you would do it besides the phishing idea you already mentioned.
Two possible approaches:
Finding the IP address could be as simple as sending an E-mail to the target and waiting for a reply. The sender IP address will often (but not always) be revealed in the mail headers.
Some larger corporations have designated IP ranges assigned to them. For American enties arin.net would be the source. Their whois service also supports wildcard search. See: Quick Guide to ARIN's Whois
In this case you will usually end up with an IP range instead of a single IP address, but it's a start.