I'd recommend Discrete Mathematics, Elementary and Beyond By Lovász, Pelikán, and Vesztergombi. It's the book I'm using in my undergraduate discrete math course, and I think it's a great introductory book that explores many areas of discrete math, and should allow you to see which field interests you most.
Discrete mathematics and any proof based math in general is what college based math should be like- if you continue to take upper level math and CS courses, you will undoubtedly face this style of math again. Plug and chug (which is what a lot of calculus is) will no longer be the norm.
There is often a very large learning curve for students who are not used to seeing this type of math- so don't stress out too much about it. Eventually, you'll break a point where everything will make (sort of) sense. I went through the exact same thing when I took discrete for the first time, and I felt like I was getting destroyed on everything (I still suck at some topics) until I suddenly hit a point of clarity where I could see how most topics were tied in together. Mathematics, and especially an introductory discrete course, is cruel in that way- that every topic you learn is inherently related to each other, so if you already fall behind just a little, the mountain to catch up just becomes incredibly massive incredibly fast- and it's hard to even pinpoint a place to even start to catch up.
You may be lost in learning elementary proof techniques, or number theory, and then the next topic (say it's graph theory) utilizes a bunch concepts and previous proofs from number theory, and then the next topic might use something proved in graph theory and number theory, and so on. All of a sudden, nothing makes sense, and to learn topic ___, you need to know graph theory, but to know graph theory, you need to know number theory, but you don't know number theory that well, and some topics in number theory can perhaps be explained by another topic in graph theory (or any topic for that matter) The chain is all interlinked and it may difficult to even see where to start- but it is for this reason that once you cross this steep barrier, most things will suddenly become clear to you.
So I'd advise you to just continue visiting professor office hours, asking more questions, asking for other students' help, doing more and more practice. It may seem like you're getting nowhere, but you're essentially learning a new language right now, so it'll obviously take sometime until you feel as if you know what you're doing. Figuring out where people get the intuition to suggest seemingly random functions or a set of numbers or some assumption will come to you slowly, and slowly you'll break more and more of this chain.
https://www.amazon.com/Discrete-Mathematics-Laszlo-Lovasz/dp/0387955852 is another book my professor enjoyed using as a supplmenet.
I use this one in my Discrete class, I think its pretty good, half the price too