Is it better to NOT have an RA, and instead be doing a TA for the first couple of years of PhD?
There are two separate issues here, and it is important to keep them separate.


You absolutely need to get involved in research as soon as possible.  The entire point of a PhD is to do research.  It's important to get into the practice of doing research from the very beginning of your PhD program, if not sooner.  Do not wait until you're done with classes.  Do not wait until you've read another book, or five more papers.  Do not wait until you have an advisor.  Start now.  Yes, your inexperience does mean that there are problems you aren't prepared to work on; work on something else.
It is not necessary and it may not even be desirable to have an assistantship to support your research.  First, you work in a research area that does not require specialized equipment or a laboratory; your research only requires time.  You can acquire that time either by acquiring a research assistantship or by signing up for research/independent study/thesis credits. If you can't do the former, do the latter; arrange your classes accordingly. Second, accepting a research assistantship may constrain you to work on one of your advisor's research projects, but you need to develop your own independent research agenda.  It's your PhD.  You need to hunt it down and kill it.


In short: You absolutely need to be doing research now.  Being an RA is of secondary importance.

(My students and I are theoretical computer scientists.)