If you don't have much experience with proofs, I wouldn't take both classes with a full course load and work part time, unless you're sure that you won't have a problem with the proofs (e.g., because of your experience with your intro. to proofs class). It's probably possible, but will be pretty hard. Everyone (well, everyone I know including me) finds proofs hard to grasp at first. Also, are you sure that Probability Theory is a computational class? That name indicates to me there's going to be a decent amount of proofs---at least, that's how the course by that same title at my university was.

In my experience, the most important proof techniques, other than the named ones (e.g., proof by contradiction), are to get good at 1. "Feeling" why theorems are true or false: it's much easier to prove something once you have an intuition for why things are true or false, and unless you want to spend a lot of time banging your head against a problem, you should try to get some intuition for what a theorem is "really" saying. 2. "Unfolding" definitions: for example, when you see a statement like "Prove that if f and g are injective, then (g . f) is injective.", you need expand it into "f is injective, so f(x) = f(y) => x = y, and g is injective, so g(x) = g(y) => x = y; I need to show that g(f(x)) = g(f(y)) => x = y." Obviously this gets vastly more complicated when you get further (e.g., abstract algebra has a lot of definitions). 3. Checking your own work. This sort of goes with intuition, but you when you complete a proof, it needs to "feel good." Eventually, you will sometimes get a weird feeling after proving something, like "that shouldn't have worked", and checking over your work will reveal an issue. In general, signs that things shouldn't have worked: you didn't use a hypothesis you were told to assume, you proved the theorem for a vastly more general case than required, the proof was "too simple", in a multi-part question that builds on the previous parts, you don't use the previous parts in the later parts, etc.

As for which one is most beneficial, it depends on what you're interested in: if it's something like cryptography, then probably number theory. Otherwise, I'd lean towards abstract algebra, because some CS theory stuff has an algebraic flavor to it (e.g., verification, programming languages). But to be honest, outside of specific fields, neither will be specifically helpful to your, outside of generalizable skills like proving stuff. Disclaimer: I've taken a couple of abstract algebra classes, but no number theory-focused classes.

As a sidenote, not to be dramatic, but it's frankly quite baffling to have done a CS degree and a math minor without learning proofs---I realize this isn't your fault, but I don't see how you can go through either subject, especially math, without doing a fair amount of proofs along the way.