XGBoost Tree 'starting feature break'
Each tree starts as a single leaf and all of the residuals go to that leaf. Then we calculate the similarity score and try to split amongst some feature characteristic. For example say we only had one feature - height. We could split the residual if its respective x-value was say height &gt; 180 or height &lt; 180. And then proceed to calculate the similarity scores and the gain for the new leaves and continue down our tree


Here it seems like you are describing just a decision tree. Watch this tutorial to understand it a bit more 


My question is now say we had two or more features such as height , age , weight , education etc. How does the algorithm know where to break the initial residuals? Does it compute it over all possible features and finds the best gain? I can imagine for large datasets to go through all features , then break it at some threshold and compare must take a long time.


Again you are talking about the decision tree and its  complexity, but yes, for large datasets is overly computationally expensive. To avoid this several strategies are used, as sampling, feature selection or quantization


Or does it start at some random feature and work its way down kind of like a random forest? I know there is a parameter within the algorithm that allows you to set the percentage of features per tree so adding on to my question once we specify this percentage how does it pick the features and more importantly once those features are picked how does it know which one to pick to break the initial leaf of residuals.


The random forest does random feature selection per split of the tree. The trees are grown greedy, so it tries all possible splits and chooses the best. If the original paper was too difficult try following this tutorial about random forest