When does code bloat start having a noticeable effect on performance?

In my experience, code bloat and execution-time bloat go hand in hand, and it's all about how the software is designed, in particular, how the data structure is designed.

If one follows the approach that every mental concept becomes a class, if one follows the notification-style pattern where simply setting a property, or adding an item to a collection, can result in a hidden ripple effect of actions propogating throughout a large non-normalized data structure network in order to try to keep it consistent, then the result will be large source code and poor performance.

On the other hand, if one tries to minimize data structure and keep it normalized (as much as reasonably possible), if to a reasonable extent, inconsistency in the data structure can be tolerated and repaired on a loosely-coupled basis, and if code generation can be used so that the program is not processing information at run time that hardly ever changes and could have been handled prior to compiling, then source code will be smaller, easily developed, and efficient.

Here's a small example where a reasonably-designed program, through a series of steps, was reduced in size by a factor of four, and made faster by a factor of 40, by eliminating data structure and using code generation.

The size of your executable doesn't really matter. It is the size of the "active" code, the code which is actually executed frequently by the application, which matters. That is a lot harder to quantify, unfortunately. For a simple approximation, you could profile your application, take the procedures which account for 90% of the execution time, and add up their code sizes.

Most modern processors have 64KB or 128KB instruction caches, so it helps to keep the active code below this size. The next threshold would be L2 size, which can be a few megabytes.