Decision and PhD. Take a once-in-a-lifetime opportunity or pursue a life dream
It seems like you're choosing between

A (nearly) guaranteed PhD offer at a middling university.
A fully funded master's program that you may or may not be accepted to, but may offer you the opportunity to jump to a better PhD program if you get the Fulbright scholarship and perform well in your master's.

Some factors you may consider are

If you take the master's offer you will spend a lot of time preparing for a PhD.  You will need to perform extra well for two years to secure your letters of recommendation, and it will look bad if you don't accomplish anything significant during that time.  In the end you might not get into your school of choice, and then you will have worked very hard for no visible gain.  How confident are you that you can (1) get the scholarship, and (2) perform consistently well once you're actually there?

A master's degree will give you more background in computer science, and you will learn more about theoretical CS than &quot;it involves both programming and mathematics.&quot;  A lot of things involve both programming and mathematics, and getting more experience (in coursework and research) will let you better evaluate your options before jumping into a long commitment.  Most theoretical CS students I know entered their PhD program knowing they wanted to study &quot;approximation algorithms,&quot; &quot;cryptography,&quot; etc, not just &quot;theoretical CS&quot; or &quot;some field that involves both programming and math.&quot;
It's also kind of a red flag that you're undecided between a PhD and a master's, and I think before you go for a PhD you should have a stronger opinion on this.  If you are uncertain about your career and your research area you will be at a significant disadvantage compared to your classmates who aren't.

If your first choice is the PhD offer, you can easily apply to both and turn down the Master's offer, but if your first choice is the Master's offer, it would be awkward to apply to both and turn down the PhD offer.