Well, I just recently picked up VF4: Evo because it was only $8. I haven't gotten really into it, mostly because I don't know anyone that plays, but I also got it in preparation for VF5, which looks fantastic.
I find that there's a lot of memorization you have to do. In Tekken, you probably only have to memorize a handful of juggles per juggle starter, but in VF you have to take into account the weight class and stance and even counterhit properties. The other depth, I think, is how the speed of throws changes everything, but you also get to buffer throw escapes, and I like doing that =P
But I haven't gotten into the complex things yet, things like Sabaki, Nitaku, and all those other lovely strange Japanese terms, nor have I properly learned how to play against other characters.
However, there is a lot of stuff in VF that I think is misread by the general public, as the tutorial covers not only VF-specific elements but general 3D fighting lessons. Things like backdashing in frame disadvantage to bait whiffs. Things like taking advantage of frame advantage to pressure. Using moves with tracking to bait steppers... all of this is wonderfully addressed in VF's training mode and is directly applicable to almost any fighting game.
As for DoA: U... it is definitely less systematically deep than Tekken. You don't have to know frames, mostly, because you only have to distinguish between moves that are throw-punishable and those that aren't (and even worse, there are guaranteed throws on BLOCK). And on hit it doesn't really matter because of stun system. Sidestepping is only useful for positioning and not for evading attacks, something that all the other 3D fighters use. The ground game in DoA:U is painfully biased towards the attacker once he learns how to counter wakeup kicks on reaction. Poking in DoA:U is limited because there are very few moves that aren't string based. I don't want to debate the stun system but it adds a tad more randomness than what I'd like.
But those are only the limitations of the fighting system. Whether it is much deeper than that, I'm not sure. SF2 has a large following despite the simple system because people manage to wring more out of it even to this day. Even strange glitchy bugs like Roll Cancelling (CvS2) and Guard Breaking (MvC2) can increase the depth of the game.
Ah, but whatever, I've been talking too much... it's time to go and see the Tekken 5 doctor... for the fourth day in a row.