My dissertation research addresses several aspects of a particular approach to the Quantum Gravity problem which is generally described as "Planck-scale physics". In fact its starting point is the possible failure of standard physics to explain phenomena as they approach the Planck scale. Planck scale physics models are usually certain deformations of standard theories which can have experimentally observable consequences and can be related to the low energy limit of of some top-to-bottom Quantum Gravity theories. My research to date has involved the study of the aspects of "deformed" field theories on a certain type of "quantum" space-times and their possible phenomenological predictions. A series of interesting results emerged when I was working on the possible interplay between these models and other Quantum Gravity scenarios, in particular in the field of black hole thermodynamics. The new methods I developed in this context turned out to have possible consequences for other frameworks like Planck-scale modifications of entropy bounds and the applications of the Holographic Principle to cosmological models of the early Universe. My research also attempts to provide a series of experimental frameworks in which the models under study can be tested and falsified. These might set phenomenological constraints in a field that until recently was open to the wildest theoretical speculations.