Does "å holde med noen" work in the present tense? I agree with you - Jeg holder med deg?
I tried to search for this expression but only found "å holde på med noen" which, as I understand, means: to check if one fits you (romantically).
In Google Translate "to agree with" is "å er enig med".
Yes it does, and I get 38k hits for "Jeg holder med deg" on Google. :)
"Å er enig med" makes no sense in Norwegian, but "å være enig med noen" also means to agree with someone, so you can say "Jeg er enig med deg".
"Å holde på med noen" is a very vague expression, much like "to mess around with someone (in a romantic or sexual manner)" in English. I can't really say that I've heard it used since high school. ;)
"Å holde på med X" in a more general sense means to be in the process of doing something, to be working on something, to occupy oneself with something. It's often interchangeable with "Å drive med X"
"Å være enig med" is more widely used, at least among the younger generation, but they're both good expressions.
While the two expressions are interchangeable in the example sentence, there is some nuance to the usage in other cases. "Å holde med noen i noe" is not used simply to agree with someone's opinion, but to support their decision (to do something); "I agree with/support your decision to...".
So, "Jeg holder med deg" can also mean "I support [you/your decision]".