A concrete example, using a simple sketch as pretext.

1. int idx = 0;
2. int[] indices;
3.  
4. void setup()
5. {
6.   size(200, 200);
7.  
8.   println("Starting init");
9.   background(255);
10.   fill(0);
11.   text("Please wait, loading...", 20, height / 2);
12.   indices = new int[width * height];
13.   // Generate a list of random indices
14.   for (int i = 1; i < indices.length; i++)
15.   {
16.     int j = int(random(0, i+1));
17.     indices[i] = indices[j];
18.     indices[j] = i;
19.   }
20.   delay(5000); // Lengthly initialization here: load stuff, compute things, etc.
21.   println("Init ended");
22.  
23.   background(255);
24. }
25.  
26. void draw()
27. {
28.   if (idx >= width * height)
29.   {
30.     println("Done!");
31.     noLoop();
32.     return;
33.   }
34.  
35.   loadPixels();
36.   pixels[indices[idx++]] = 0xFF000000 + idx * 64; //#000000;
37.   updatePixels();
38. }

We don't see the message, because draw() hasn't started.
So we can do the drawing in two parts, as GoToLoop said:

1. int idx = 0;
2. int[] indices;
3. int startPhase = 0;
4.  
5. void setup()
6. {
7.   size(200, 200);
8. }
9.  
10. void draw()
11. {
12.   switch (startPhase)
13.   {
14.   case 0: // Display message in this frame
15.     println(startPhase);
16.     background(255);
17.     fill(0);
18.     text("Please wait, loading...", 20, height / 2);
19.     startPhase++;
20.     return;
21.   case 1: // Do the setup
22.     println(startPhase);
23.     setUpSketch();
24.     startPhase++;
25.     return;
26.   case 2: // Doing the setup
27.     println(startPhase);
28.     return;
29.   }
30.  
31.   if (idx >= width * height)
32.   {
33.     println("Done!");
34.     noLoop();
35.     return;
36.   }
37.  
38.   loadPixels();
39.   pixels[indices[idx++]] = 0xFF000000 + idx * 64; //#000000;
40.   updatePixels();
41. }
42.  
43. void setUpSketch()
44. {
45.   println("Starting init");
46.   indices = new int[width * height];
47.   // Generate a list of random indices
48.   for (int i = 1; i < indices.length; i++)
49.   {
50.     int j = int(random(0, i+1));
51.     indices[i] = indices[j];
52.     indices[j] = i;
53.   }
54.   delay(5000); // Lengthly initialization here: load stuff, compute things, etc.
55.   println("Init ended");
56.   startPhase++;
57.   background(255);
58. }

The phase 2 is actually skipped, because the setup phase is blocking the sketch.
And the wait screen is a bit static...
We can do an animation, while doing the init in a separate thread:

1. int idx = 0;
2. int[] indices;
3. int startPhase = 0;
4.  
5. void setup()
6. {
7.   size(200, 200);
8. }
9.  
10. void draw()
11. {
12.   switch (startPhase)
13.   {
14.   case 0: // Start the setup
15.     println(startPhase);
16. //    setUpSketch();
17.     thread("setUpSketch");
18.     startPhase++;
19.     return;
20.   case 1: // During the setup
21. //    println(startPhase);
22.     showLoading();
23.     return;
24.   }
25. //  println("-  " + startPhase);
26.  
27.   if (idx >= width * height)
28.   {
29.     println("Done!");
30.     noLoop();
31.     return;
32.   }
33.  
34.   loadPixels();
35.   pixels[indices[idx++]] = 0xFF000000 + idx * 64; //#000000;
36.   updatePixels();
37. }
38.  
39. void setUpSketch()
40. {
41.   println("Starting init");
42.   indices = new int[width * height];
43.   // Generate a list of random indices
44.   for (int i = 1; i < indices.length; i++)
45.   {
46.     int j = int(random(0, i+1));
47.     indices[i] = indices[j];
48.     indices[j] = i;
49.   }
50.   delay(5000); // Lengthly initialization here: load stuff, compute things, etc.
51.   println("Init ended");
52.   background(255);
53.   startPhase++;
54. }
55.  
56. int loadingX = 20;
57. void showLoading()
58. {
59.   background(255);
60.   fill(0);
61.   text("Please wait, loading...", 20, height / 2);
62.   fill(#0000AA);
63.   ellipse(loadingX, 2 * height / 3, 20, 20);
64.   loadingX += 2;
65.   if (loadingX > width - 20)
66.   {
67.     loadingX = 20;
68.   }
69. }

Note: don't name the setup function "init", it is a method used internally by Processing.