Is it possible for a missing #include to break the program at runtime?

Yes, it's perfectly possible. I'm sure there are lots of ways, but suppose the include file contained a global variable definition which called a constructor. In the first case the constructor would execute, and in the second it wouldn't.

Putting a global variable definition in a header file is poor style, but it's possible.

Yes, that's possible.

Everything concerning #includes happens at compile time. But compile time things can change behavior at runtime, of course:

some/code.h:

#define FOO
int foo(int a) { return 1; }

then

#include <iostream>
int foo(float a) { return 2; }

#include "some/code.h"  // Remove that line

int main() {
  std::cout << foo(1) << std::endl;
  #ifdef FOO
    std::cout << "FOO" std::endl;
  #endif
}

With the #include, overload resolution finds the more appropriate foo(int) and hence prints 1 instead of 2. Also, since FOO is defined, it additionally prints FOO.

That's just two (unrelated) examples that came to my mind immediately, and I'm sure there are plenty more.

Just to point out the trivial case, precompiler directives:

// main.cpp
#include <iostream>
#include "trouble.h" // comment this out to change behavior

bool doACheck(); // always returns true

int main()
{
    if (doACheck())
        std::cout << "Normal!" << std::endl;
    else
        std::cout << "BAD!" << std::endl;
}

And then

// trouble.h
#define doACheck(...) false

It's pathological, perhaps, but I've had a related case happen:

#include <algorithm>
#include <windows.h> // comment this out to change behavior

using namespace std;

double doThings()
{
    return max(f(), g());
}

Looks innocuous. Tries to call std::max. However, windows.h defines max to be

#define max(a, b)  (((a) > (b)) ? (a) : (b))

If this was std::max, this would be a normal function call that evaluates f() once and g() once. But with windows.h in there, it now evaluates f() or g() twice: once during the comparison and once to get the return value. If f() or g() was not idempotent, this can cause problems. For example, if one of them happens to be a counter which returns a different number every time....

Binary incompatibility, accessing a member or even worse, calling a function of the wrong class:

#pragma once

//include1.h:
#ifndef classw
#define classw

class class_w
{
    public: int a, b;
};

#endif

A function uses it, and it is ok:

//functions.cpp
#include <include1.h>
void smartFunction(class_w& x){x.b = 2;}

Bringing in another version of the class:

#pragma once

//include2.h:
#ifndef classw
#define classw

class class_w
{
public: int a;
};

#endif

Using functions in main, the second definition changes the class definition. It leads to binary incompatibility and simply crashes at runtime. And fix the issue by removing the first include in main.cpp:

//main.cpp

#include <include2.h> //<-- Remove this to fix the crash
#include <include1.h>

void smartFunction(class_w& x);
int main()
{
    class_w w;
    smartFunction(w);
    return 0;
}

None of variants generates a compile or link time error.

The vice versa situation, adding an include fixes the crash:

//main.cpp
//#include <include1.h>  //<-- Add this include to fix the crash
#include <include2.h>
...

These situations are even much more difficult when fixing bug in an old version of program, or using an external library/dll/shared object. That's why sometimes must be followed the rules of binary backward compatibility.

It's possible to be missing a template specialization.

// header1.h:

template<class T>
void algorithm(std::vector<T> &ts) {
    // clever algorithm (sorting, for example)
}

class thingy {
    // stuff
};

// header2.h

template<>
void algorithm(std::vector<thingy> &ts) {
    // different clever algorithm
}

// main.cpp

#include <vector>
#include "header1.h"
//#include "header2.h"

int main() {
    std::vector<thingy> thingies;
    algorithm(thingies);
}

I want to point out that the problem also exists in C.

You can tell the compiler a function uses some calling convention. If you don't, the compiler will have to guess that it uses the default one, unlike in C++ where the compiler can refuse to compile it.

For example,

main.c

int main(void) {
  foo(1.0f);
  return 1;
}

foo.c

#include <stdio.h>

void foo(float x) {
  printf("%g\n", x);
}

On Linux on x86-64, my output is

0

If you omit the prototype here, the compiler assumes you have

int foo(); // Has different meaning in C++

And the convention for unspecified argument lists requires that float should be converted to double to be passed. So although I gave 1.0f, the compiler converts it to 1.0d to pass it to foo. And according to System V Application Binary Interface AMD64 Architecture Processor Supplement, the double gets passed in the 64 least significant bits of xmm0. But foo expects a float, and it reads it from the 32 least significant bits of xmm0, and gets 0.