How would substitution reaction results differ between reacting halides with a tertiary bromoalkane vs reacting it with a primary bromoalkane? Say, you conducted two separate reactions; in one, you combined $\mathrm{50~mmol}$ saturated $\ce{KCl}$ solution with $\mathrm{10~mmol}$ 1-bromooctane (assume heating), and in the other you combined $\mathrm{10~mmol}$ saturated $\ce{KI}$ solution with $\mathrm{10~mmol}$ 1-bromoctane. In both cases $\mathrm{0.5~mmol}$ hexadecyltributylphosphonium bromide was used as a catalyst.

So, due to relative charge densities and the fact that the electrophillic carbon is primary, you would have a low yield of 1-chloroocatane vs starting material in reaction 1 and you would have a high yield of 1-iodooctane vs starting material in reaction 2, both cases obtained via SN2 reaction.

Now, suppose you would have repeated the same two reactions, only this time you would have reacted the $\ce{KCl}$ and $\ce{KI}$ with 2-bromo, 2-methyloctane, how exactly would the results differ from the results of the previous two reactions, or would they have been the same?

I know that the reaction would have no "choice" but to react via the SN1 (or perhaps E1) route, as the electrophillic carbon is tertiary and thus very sterically hindered. Also, I know that $\ce{I-}$ ions are good nucleophiles, but that doesn't matter in this case, does it?

Perhaps this reaction would go slower than the previous, owing to the fact that it requires the $\ce{Br-}$ to dissociate, and therefore there would be lower yields of both haloalkane products. But then again, wouldn't it go faster owing to the fact that it is in a polar protic solvent, and that the formed carbocation would be tertiary?
There are (at least) four major factors to consider in predicting the results of these reactions: (a) the nature of the substrate, (b) the strength of the nucleophile, (c) the quality of the leaving group, and (d) solvent effects. Halides are able to function, to varying degrees, as both good leaving groups and strong nucleophiles.

In protic solvents, negative charges are stabilized by the $\ce{\delta^{+}}$ of the solvent hydrogens bonded to some electronegative atom (conventionally limited to $\ce{N, O, F}$). Since nucleophiles carry either a full or partial negative charge, protic solvents tend to reduce the reactivity of nucleophiles. Because smaller nucleophiles are more easily and thoroughly solvated than large and polarizable nucleophiles, the effect on them is more drastic. Consequently, in protic solvents, the relative nucleophilicity of the halides is generally given as $\ce{I- &gt; Br- &gt; Cl- &gt; F-}$. In aprotic solvents, the reactivity is precisely the opposite. Hence, the proper selection of solvent is crucial. In your first example, there is no particular reason I can think of to suppose that the yield of 1-chlorooctane would inevitably be low. Indeed, in an aprotic solvent, the usual choice for SN2 reactions, $\ce{Cl-}$ can be expected to be a stronger nucleophile and poorer leaving group than $\ce{Br-}$. I would expect the yield to be good, especially with an excess of $\ce{KCl}$.

On the matter of the substrate, with a tertiary carbon, SN2 is all but completely impossible. In that situation, elimination reactions are typically favored if some base is present. The halides, however, are extremely weak bases (being the conjugate bases of strong acids), so if a non-basic solvent is selected, substitution by an SN1 mechanism seems most probable. Selection of a relatively non-basic, non-nucleophilic protic solvent would be ideal. (Off the top of my head, DMSO comes to mind, which is only weakly nucleophilic, especially by comparison to the halides.) You're right that the strength of the nucleophile is not the deciding factor in an SN1, since the rate-determining step is the loss of the leaving group and the resultant carbocation formation. In a protic solvent, $\ce{I-}$ should theoretically be more effective as a nucleophile than $\ce{Cl-}$. However, I would still expect the latter reaction to work, particularly if the concentration of $\ce{Cl-}$ is high. I'm fairly confident that the difference in reactivity between, e.g., $\ce{Cl-}$ and $\ce{Br-}$ would be largely negated if the former is available in vastly larger concentration in the solution.

Edit: On a second reading, I just noticed that you labeled the halide solutions as aqueous. I don't know if that's deliberate, but I don't think that would make sense. For one thing, the reagents (namely, the haloalkanes) would be largely insoluble in water. Second, because water is an amphoteric species, it could be potentially reactive.