My experience has been if you perform well in your residency (internal medicine) you should have no problem getting into one of the fellowship subspecialty programs that you discussed. Internal medicine is a very diverse residency and offers a great deal of fellowship opportunities.
As far as surgical, you normally must complete a surgical internship/residency program prior to any surgical fellowship. These are lengthy...5-7 years, but on average have much higher salaries upon completion. I just have personal reservations about a DO wanting to be a surgeon. To me, DO's are better trained and screened to be highly interactive with there patient's in a primary care setting. Hope this helps!