Start with statistics by David Freedman. It is very approachable as an introduction, not too theory heavy, can get a handle on all of the "main" issues. Afterwards, you have 2 options:

1) Do you want "theoretical" knowledge(math background required)? If so, then you need to get a decent mathematical statistics book like Casella-Berger. I think a good US CS degree grad could handle it, but you might need to go a bit slow and google around/ maybe fill in some gaps in probability/calculus.

2)Introduction to Statistical Learning is unironically a great intro to "applied" stats. You have most of the "vanilla" models/algorithms, theoretical background behind each but not too much, you can follow along with the R version and see how stuff actually works and exercises that vary in difficulty.

With regards to Gelman and Bayesian data analysis, I should note that in my experience the Bayesian approach is 1st year MS /4th year of a Bachelors in the US. It's very useful to know and have in your toolbox but IMO it should be left aside until you are confident in the "frequentist" basics.

Start here:

https://www.inference.org.uk/itprnn/book.pdf

It's a little dated now but it connects Bayesian statistics with neural nets and information theory in an elegant way.

Probability Theory by Jaynes if you'd like more bayes

I think Statistical Rethinking [0] is a far more approachable first entry. The author posts his video lectures on Youtube which are excellent and should be watched with the book. The book gets way less into the mathematical weeds than other texts, so a working statistician would require something deeper.

[0] https://en.wikipedia.org/wiki/Statistical_Rethinking