You don't need the Run dialog, the pinned taskbar icons or even live tiles in the Windows 8 Start screen; you just need to start typing.
Press the Start button, start typing the name of the app you want, or the file you want, or the control panel setting, and a list of matches appears on the Start screen (app first, but you can click Documents and Settings in the filter on the right - or choose any of the apps that have a search contract in the list to see specialised results). Start typing the file name of the app instead, and once you've typed the full file name an icon will appear for it after about two seconds. For EXE files like DXDIAG and REGEDIT, you don't even need the .EXE on the end; for consoles like GPEDIT.MSC you need the filename with extension.
Once you've got that icon you can tap or click to run the app. Or you can swipe upwards on the icon and choose Advanced to pin it to the taskbar (which also adds it to the Start screen) or Run as Administrator.
If you find the Start screen a bit too distracting - sorry, alive and compelling - try pressing Windows-Q to get a column listing of apps; you can still start typing to filter apps, just without the risk that a scrolling update wil grab your attention.