The most viable upgrades, without delving into the extremely sifi stuff like antimatter or artificial black holes, would be Nuclear. Exactly how that goes depends on how strictly you want to stick to proven technology. This gives you a variety of Nuclear rockets, and potentially building your own Laserway at the most hypothetical end. And those all run into the problem of how you obtain materials.
The trouble with Fission-powered rockets is the amount of mass required. If your android et al are more radiation-resistant than meat-people, you won't need anywhere near the shielding that a manned Nuclear rocket requires. Otherwise, you'll need tons of material just for shielding. More importantly, you'll need Fissile material, which is both rare and heavy. Not to mention all the material required to get the reaction to behave in a manageable, high thrust way. That material, other than perhaps water or hydrogen if you use a TNR that requires those, are likely to be harder to obtain once you're far enough out that everything is either ice or gas. It also costs more fuel to accelerate. And if you are planning ahead and obtaining your Fission materials before you're far from home, you could probably have just waited and built the thing before leaving the system in the first place. It's doable, especially if you assume the necessary materials are easier to extract from Kuiper Belt or Oort Cloud objects than it seems, but it's going to cost you a great deal of initial fuel, if you aren't just flying out to a Uranium-rich asteroid, building it there, then leaving.
If you permit efficient Fusion, things are a little easier, though you still need to worry about the materials comprising your reactors. Fusion pushes the bounds of what we know to be viable, so it might not be realistic enough at present for your purposes, but it is the best bet for getting up to decent interstellar velocities, and the fuel is much easier to come by. It's questionable if you could source Fission materials from random mountains of ice in deep space (Pluto seems to have radioactive materials in its core, but most stuff out there is probably less Pluto and more comet-like in makeup). If you can build Fusion-powered lasers in the icy bodies you encounter along the way, you could benefit from all that Fusion fuel without having to drag it along with you (either use the lasers to beam materials to your ship, or use them as propulsion directly to push on light-sails).
All of the above practically require the ability to send out drones to gather materials. Your ship is going to be big, fast, and on a tight fuel budget until you can get Fission or Fusion up and running. This feels like a point in favor of Laserways to me, since those allow you to send information and small amounts of material to and fro without needing to worry as much about fuel, but doing that practically without being able to build excellent Fusion reactors in deep space objects is probably implausible.
TLDR: It's certainly doable, but challenging, due mostly to the reasons that anything involving chemical-powered spaceflight is challenging. If upgrading is the plan from the very beginning, this would help. There are several Fission-powered rocket designs you could use, and Fusion makes it easier to obtain materials further from home.