The solution: DPI.
For gnome: Go to System->Preferences->Appearance->Fonts->Details and change the 'resolution: dots per inch' value.
For xfce: Go to Applications->Settings->Appearance->Fonts and change the 'Custom DPI Settings' value.
xdpyinfo | grep resolutionand
xrdb -queryare useful for determining your current DPI values.
You can also fiddle with the system font settings, and in Firefox you can change Edit->Preferences->Content->Fonts&Colors->Advanced->Minimum font size. You can also change Firefox's zoom level with Ctrl-Alt-+ and Ctrl-Alt--. Ctrl-Alt-0 will set the zoom back to zero. By default the zoom settings are rembered on a per-site basis, but you can change this in about:config.
For your terminal fonts, you can use the fixed width system font settings, or change your terminal profile with Edit->Profile Preferences.