Living cells are crowded with dynamic distributions of macromolecules and organelles that influence protein diffusion, molecular transport, biochemical reactions, and protein assembly. Here, we test the hypothesis that the diffusion of single molecules deviates from Brownian motion as described by the Stokes-Einstein model in a manner that depends on the viscosity range, the chemical structure of both the diffusing species and the crowding agents, and the spatio-temporal resolution of the employed analytical methods. Our size-dependent fluorescent probes are rhodamine-110, quantum dots, enhanced green fluorescent proteins (EGFP), and mCerulean3-linker-mCitrine FRET probes with various linker length and flexibility. Using fluorescence correlation spectroscopy (FCS), we investigated the translational diffusion of structure-dependent fluorescent probes, at the single-molecule level, in homogeneous (glycerol) and heterogeneous (Ficoll-70) solutions as a function of the bulk viscosity. Complementary rotational diffusion studies using time-resolved anisotropy enable us to assess weak interactions in crowded and viscous environments. Overall, our results show negative deviation from the Stokes-Einstein model in a fluorophore- and environment-dependent manner. In addition, the deviation between the FCS-measured hydrodynamic radius of the FRET probes in a buffer at room temperature and the molecular-weight based estimate (Perrin equation) as the number of the amino acid residues in the linker increases. These studies are essential for quantitative biophysics using fluorescence- and diffusion-based studies of protein-protein interactions and biomolecular transport in living cells.