I have virtually no understanding of how batteries work and charge, and have various questions on them

When charging over a USB port which is also used for communication, you're limited to 2.5W/500mA. When using a port dedicated for charging (which can be a female USB-A plug), you can use almost 10W/2A. From these numbers, the dedicated charger is clearly better.

However, batteries have thermal and chemical properties which often limit the charge rate to something less than these values. This is especially true for small batteries in confined spaces like your cell phone battery, and the lithium-ion chemistry which is likely used has the added potential of explosive thermal failure, so the charge rate is limited by some circuitry.

It would be reasonable to assume that the maximum charge rate for your cell phone battery is a little less than 2A and more than 500mA. Cell phone batteries are usually charged at about 1C, and the maximum cell voltage of a Li-ion is about 4.2V, so assuming a 1000mAh battery and a 90% efficient charger (which is generous), you'd need 4.6W of power to charge your battery as fast as possible.

Charging more slowly than this (i.e. at 2.5W) shouldn't diminish the charge level of the battery in any noticeable way. A software power meter could be erroneously reporting a higher battery life due to heating of the battery and the consequent higher voltage, or any number of other errors. If an accurate test (identical use patterns, signal strength, previous charge levels, etc) indicates that your phone has markedly less battery life after charging by USB, then either your battery is defective or your phone circuitry is poorly designed.

LiIon is usually charged at constant current until a max allowed voltage is reached and then is held at that voltage while current tails off under "control" of chemistry of battery until Ichg = k% of Imax where k% is chosen according to longevity or max energy concerns.50% or 25% of Imax gives longer life. 10% or 5% tail gives max capacity but lower life.

Lowering Vpedesatl by 0.1V greatly assists battery life.

Discharging to higher cutoff voltage aids cycle life.

LiIon also has calendar life and starts self destructing from day one so a lightly used battery still dies.

Best cycle life is achieved by stopping charge when Vpedestal is reached and systen changes from CC to Cv. By monitoring voltage this point can be observed. You could even do a "dumb" system that simply watched delta Vbat and declared constant V when delta fell to zero. Only slightly more than a comparator and an RC delay in one input would achieve that.(While Vin is ramping a delayed vin is lower. When Vin pedestals the delayed Vin almost catches up. An offset voltage is needed to allow comparator towork).

LiIon cells mechanically flex the cell as metallic Lithium is "plated" in and out of the cell*. Cycle life is in large part due to battery beating itself to death mechanically.(This is why LiFePO4 lasts much longer and has lower capacity - the material is held in an Olivine matrix that maintains constant shape as active material is moved in/out BUT it takes up some space. )

*Note: Bill Dubuque has suggested that this sentence would be better replaced with " 'LiIon cells mechanically flex the cell as Lithium ions are intercalated".
The distinction is a finer one than may be apparent. However, it is true to say that if you cut open a LiIon cell you would not usually find metallic Lithium in it. Bill notes that this makes primary Lithium cells, which do contain metallic Lithium, a greater fire hazard than LiIon cells.
If you charge a LiIon cell with excessive voltage metallic Lithium will be 'plated out' and "vent with flames" mode usually occurs at about the same time.

Charge to CV level as often and as soon as possible.

If charging all the way their "disconnect message" is a sign of bad ethos. They are probably trying to minimise the risk of fire without telling you.

For longest storage life (as opposed to long life in regular use) storing at a lower voltage than Vmax is in order. Probably at about 3.6 V and only about 30% state of charge. The various Mars Rovers use LiIon batteries and have a design life of about 8000 cycles - but charge to about 3.6 - 3.7 V maximum.
8000 / 365(~=) ~= 22 Terran years.