While some suggestions have included tkinter and wxPython, the other part of the answer to your question is that you will also need to package it using something like py2app, pyinstaller, or py2exe (depending on the operating system). You mentioned the other machines do not have python, so this would be required in order to distribute the entire python environment with your app.
Also have a look at PySide or PyQt. They have a ton of tutorials everywhere and heavy documentation from Qt.