You got the right intuition. Here is how to do it formally:
Removing $\epsilon$-transitions is standard and easy to do. Lets say that the resulted NFA $A = \langle \Sigma, Q, Q_0, \delta, F\rangle$ that you get has more than one initial state, that is $|Q_0| > 1$. In this case, you can modify $A$ to get an equivalent automaton with a single initial state, simply by adding one more state, and without using $\epsilon$-transitions:
Define the NFA $B = \langle \Sigma, Q\cup \{q_{new}\}, \{q_{new}\}, \eta, F\cup \{ q_{new}: Q_0\cap F\neq \emptyset\}\rangle$, where $q_{new}\notin Q$ , and for every letter $a\in \Sigma$ and state $q\in Q$, it holds that:
1- $\eta(q_{new}, \sigma) = \bigcup\limits_{q\in Q_0} \delta(q, \sigma)$.
2 - $\eta(q, \sigma) = \delta(q, \sigma)$.
So essentially $B$ is obtained from A by adding a new state $q_{new}$, which is the only initial state of $B$. Upon reading $\sigma$ from $q_{new}$ we move nondeterministically to any state that we can reach in $A$ from $Q_0$ upon reading $\sigma$, and finally $q_{new}$ is considered accepting only when there is an initial state in $A$ that is accepting (this part handles the empty-word $\epsilon$).
Correctness follows easily. I leave the empty-word case for you, and simply note that once $B$ leaves the state ${q_{new}}$, it cannot go back to it, and has to proceed by following transitions of $A$.
Now every accepting run of $A$ can be replaced by an accepting run of $B$ -- you only have to replace the initial state of the run with $q_{new}$, and then verify that the resulted run is legal in B and accepting. Conversely, every accepting run $r$ of $B$ on a non-empty word has a corresponding accepting run of A on the same word: if $q_{new} \xrightarrow{a} q$ is the first transition that $r$ traverses, then by definition, there is some $q_0\in Q_0$ such that $q\in \delta(q_0, a)$ and thus we can replace the transition $q_{new} \xrightarrow{a} q$ with $q_0 \xrightarrow{a} q$ to get an accepting run of $A$.
So what you should do first is define formally the automaton that you think works, and then try to prove that it is indeed equivalent. I leave the details to you.
Note that what I actually did is removal of $\epsilon$-transitions -- it can be done in several ways, but if you care about a single initial state, that can also be done, as we showed.
