The following is likely an unpopular opinion:
Keep in mind that a PhD in CS will give you legitimate understanding of the principles and will enable you to create answers for new problems. Any derivatives like bioinformatics and others will leave you ill-equipped to do this and will focus more on specific applications of CS methodology, relatively speaking.
This is parallel to the people who ask about MD-MPH or MD-PHD in epi to basically have the role as clinician-statistician when the real answer is MD-MS(or PhD) in biostatistics or statistics. The first two options focus more on specific applications but leave you high-and-dry in the areas of true understanding and the ability to come up with new solutions for problems. If you want to be a physician-computer scientist, get the PhD in CS and you can apply it to biomedical problems more effectively. If you want to be a physician-researcher with a good working knowledge of applications of CS to medicine, get a derivative degree. However, it's very hard to go from a less knowledgeable/in-depth degree to a more knowledgeable (i.e. you won't likely every be a computer scientist if you get a bioinformatics degree).
Disagree. Working in bioinformatics/genomics can give you a "legitimate" understanding of the underlying computer science principles as well as train you in how to "create answers for new problems".
CS is a field that includes many subdisciplines. Regardless of what you do, you can't everything in CS. Someone who does research in systems may not necessarily be knowledgeable about algorithms (simply because that's not there focus!). You might say: but if you know theory, you know everything? You'll write proofs and all, but that will be your area of research (and even in theory, there are many subfields so you'll be focused on a subproblem within all there is to know about CS theory). You will not be the best equipped to do research in machine learning algorithms -- which, in itself, is a field that requires decades to master (and integrates probability theory, statistical theory, in addition to computer science).
My point? Pinpoint what interests you. Focus on that! It doesn't necessarily mean you understand a broader field less well. You will always understand less about the things that you aren't specifically doing research in, and that's fine -- you aren't expected to know everything.
Many of the top computational biologists have PhDs in pure math or pure CS. That's simply because computational biology / bioinformatics / genomics are relatively new fields. They ended up doing most of their research in solving problems in biology (and coming up with ways to solve such problems) so you don't see them writing papers on NP-completeness (and they likely haven't touched a lot of the CS theory in years unless they teach it to undergrads).
During your PhD, you learn the most from the lab you do research in. The poster above seems to think that if you choose a computational biology lab, you are therefore less equipped to solve questions in computational biology. Nothing can be further from the truth. The people who developed algorithms to analyze microarray and RNA-seq data are considered computational biologists, and are also considered statisticians / computer scientists. Some of them have compbio degrees, some have math degrees, and some have CS degrees. Another example: Latent Dirichlet Allocation was discovered by both computational biologists and computer scientists.
At my undergrad school (a top 5 where I earned a CS master's degree by the way), there was a lot of overlap between the bioinformatics and the CS PhD (or even between the bioinformatics and the CS master's). You could earn a degree in either and work under a CS Prof who develops algorithms to analyze genomics data. If you did bioinformatics though, you likely just wouldn't be working under a professor whose main research focus is cryptography.
That being said, I do agree with the above poster about the MPH/Epi comparison to statistics. That part is true -- but CS vs. computational biology is a completely different story.
So the question to the original poster is what he wants to do with CS. CS is a broad field. That's like saying "I want to do research in biochemistry". But there's no reason to think that (s)he should spend a decade of his/her life reading landmark mathematical proofs before trying to train deep learning models for genome motif discovery.